使用遗传算法的背包问题 [英] knapsack problem using genetic algorithm

问题描述

您好！



我是代码项目的新成员。我刚开始使用遗传算法。



我需要在c ++中使用遗传算法解决背包问题。



例如，我正在初始化人口：

Hello!

I am a new member of code project. I have just started working with genetic algorithm.

I need to solve knapsack problem using genetic algorithm in c++.

For example, I am initializing the population:

void initialize_Q()
{
    double r,num=0.0;
    for( int
        i=0;i<POPsize ;i++)
    {
        for(int j=0;j<NUM_BIT;j++)
        {
            r=rnd0_1();
            if(r>=0.5)
            {
                population[i].P[j]=1;
                num++;
                if(num>CAPACITY)
                    population[i].P[j]=0;
            }
            else
                population[i].P[j]=0;

        }
    }

}

如果我使用遗传过程，我无法弄清楚如何评估适应度值。我应该随机创建利益和价值，然后转换十进制数。二进制？



任何有关基本思想的帮助，或者c ++中的任何实现都会有很大的帮助。

I just cant figure out how to evaluate the fitness value if I use genetic process. And should I create benefit and value randomly and then convert decimal no. to binary?

Any help with the basic idea, or any implementation in c++ would be of great help.

推荐答案

尝试查看此。以前有人问过。



干杯。

Try checking out this. It has been asked before.

Cheers.

对于任何GA的适应度函数，你必须定义一个返回的算法最佳解决方案的最大值（或最小值，取决于问题类型）值。



对于背包问题，适合度通常定义为所有的总值物品包装，最佳解决方案将是最健康的解决方案。这应该回答你的问题：只需编写一个计算所有打包物品价值总和的函数。



这是最简单的部分。



当你考虑如何创造下一代时，它会变得更加棘手，因为你必须注意背包的限制。一种方法是指定特殊的遗传算子，确保后代自动满足限制。第二步将是一个额外的步骤，清除所有违反限制的后代，然后继续生产后代，直到你有足够数量的新解决方案。



你可以通过允许超过背包容量的坏解决方案，而不是对健身功能结果添加惩罚，例如，将硬限制转为软限制。 g。

For the fitness function of any GA you have to define an algorithm that returns the maximum (or minimum, depending on the kind of problem) value for optimal solutions.

For the knapsack problem, the fitness is typically defined as the total value of all items packed, and the optimal solution would be the one with the highest fitness. This should answer your question: simply write a function that calculates the sum of the value of all packed items.

That's the easy part.

It gets more tricky when you consider how you're going to create the next generation, since you have to watch out for the knapsack limitations. One way would be to specify special genetic operators that ensure that the offspring automatically fulfils the restriction. A second would be an additional step that weeds out all offspring that breach the restrictions, and then keep producing offspring until you have a sufficent number of new solutions.

You could also turn the hard limit(s) into a soft limit by allowing 'bad' solutions that exceed the capacity of the knapsack and instead adding a penalty to the fitness function result, e. g.

modified_fitness = max_fitness*A - excess_of_limits*B

其中 max_fitness 是对可达到的最大适应度值的估计（使用非平衡适应度函数）， A 是一个小到足以将该估计值降低到实际可实现值以下的减少因子（显然取决于你可以估计的程度 - 大多数情况下0.5到0.9之间的某个值应该有效， excess_of_limits 是评估的解决方案超出背包限制的数量，以及 B 是一个缩放因子，将超出部分与健身值的近似大小相关联。



找到好处这些常量的值可能需要一些试验（和错误）。或者您可以要求用户在运行时输入这些值，这样您就不必重复更改程序。

where max_fitness is an estimate for the maximum achievable fitness value (using the unpenalized fitness function), A is a reducing factor small enough to reduce that estimate well below realistically achievable values (obviously depends on how well you can estimate - some value between 0.5 and 0.9 should work for most cases), excess_of_limits is the amount by which the evaluated solution exceeds the knapsack limits, and B is some scaling factor putting the excess into relation to the approximate size of the fitness value.

Finding good values for these constants will probably require some trial (and error). Or you could ask the user to enter these values at runtime, so you don't have to repeatedly change the program.

这篇关于使用遗传算法的背包问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！