使用遗传算法求解多峰函数的最大值，是我的一项课程作业，做完之后，顺便把文档整理出来做个记录。全部内容如下：
 
1、问题描述
 
编程实现遗传算法，并求解多峰函数的最大值。多峰函数的表达式如下所示：
 
 用MATLAB做出函数的图像如下：
 
 
2、算法描述及实现
 
2.1、遗传算法概述
 
遗传算法(GA，Genetic Algorithm)，也称为进化算法。遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作，因此不同于其他求解最优解的算法，遗传算法不存在求导和对函数连续性的限定，采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。
 
以上是对遗传算法相对抽象的总结，为了更具体形象的解释遗传算法的一般原理，我们首先介绍一些生物学上的概念：
 
①种群：不同生物个体形成的群体，生物的进化以群体的形式进行，这样的一个群体称为种群；
 
②个体：组成种群的单个生物；
 
③基因：带有遗传信息的DNA片段，可以通俗的将基因理解为一段信息，这段信息决定的生物个体的性状；
 
④表现型：根据基因形成的个体的外部表现；
 
⑤适应度：生物个体对于生存环境的适应程度，越适应那么其得以存活和繁衍的概率就越大；
 
⑥遗传：通过繁殖过程，子代将从父母双方各获取一部分基因，形成新的自己的基因，这个过程中，会发生基因的复制、交叉，也会以较低的概率发生基因突变；
 
⑦自然选择：物竞天择，适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少；
 
⑧进化：种群通过代际繁衍不断适应生存环境的过程，在这个过程中，以对外界环境的适应度为评判标准，生物的性状不断得到改良。
 
了解了这些术语的含义，我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的，即生物只能改变自己去适应环境，那么在自然选择的过程中，适应度低的个体会被淘汰，适应度高的个体被保留，高适应度的父体与母体又有更高的概率繁衍出适应度高的子代，因此在一代又一代的繁衍之后，高适应度的个体在种群中所占的比例越来越大，种群就这样完成了进化。
 
现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此，遗传算法的思路是，将要解决的问题模拟成一个生物进化的过程，通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例：
 
将(x, y)这一可能的解作为一个个体；将多峰函数的函数值f(x, y)作为个体的适应度；对(x, y)进行编码作为个体的基因；以适应度为标准不断筛选生物个体；通过遗传算子（如复制、交叉、变异等）不断产生下一代。如此不断循环迭代，完成进化。最终，根据设定的迭代次数，可得到最后一代种群，该种群中的个体适应度都较高，而多峰函数的最大值就有比较大的概率存在于这一群解中，以种群中适应度最高的个体作为问题的解，则可以说该解有比较高的概率就是我们希望求得的最优解。
 
文字述说终究还是不如图表好理解，因此还是看图吧（下图将本题与自然遗传联系了起来）：
 
 通过以上描述，我们不难看出，遗传算法不能保证一定能求得最优解，而只能以一定的概率求最优解。但是使用遗传算法时，我们可以不用关心具体如何去找最优解，要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。
 
2.2、算法的流程
 
通过上文的阐述，对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤，并一一解析：
 
第一步：随机产生一个种群，作为问题的初代解（通常，初代解可能与最优解相差较大，这是可以容忍的，只要保证初代解是随机产生的，以确保个体基因的多样性即可）；
 
第二步：寻找一种合适的编码方案对种群中的个体进行编码，可以选择如浮点数编码或二进制编码等常用编码方案（需要指出的是，不同的编码方案直接影响后续遗传算子的实现细节）；
 
第三步：以多峰函数的函数值 作为个体的适应度，计算种群中每个个体的适应度（算出的适应度将为后续的个体选择提供依据）；
 
第四步：根据适应度的高低选择参与繁衍的父体与母体，选择的原则是适应度越高的个体越可能被选中（以此不断淘汰适应度低的个体）；
 
第五步：对被选出的父体与母体执行遗传操作，即复制父体与母体的基因，并采用交叉、变异等算子产生出子代（在较大程度保留优秀基因的基础上，变异增加了基因的多样性，从而提高找到最优解的概率）；
 
第六步：根据一定的准则判断是继续执行算法，还是找出所有子代中适应度最高个体作为解返回并结束程序（判断的准则可以是设定的解的阈值、指定的迭代次数等）。
 
 
2.3、算法的编码实现
 
2.3.1、编码
 
本文采用的是二进制编码方式，这种编码方式编解码过程简单易行，相应的交叉算子、变异算子等操作用位运算即可实现。当然，它也有一定的缺点，比如连续性不够强。为保证求解的精度，本文使用14个bit为 编码，使用11个bit为 编码，两者组合成25个bit的最终结果。不难算出，该方式的编码精度可达千分位。具体的编码操作可总结为，将 或 的取值区间映射到0~2n-1这一整数范围，其中n表示编码位数， 或 在其取值区间的某点，相应的映射到整数区间中的某点，改点即为 或 的基因编码。程序如下：
 
/*
    基因编码
    gene1       输入型参数，待编码的基因段1
    gene2       输入型参数，待编码的基因段2
    gene_code   输出型参数，基因编码

    返回值：当输入的基因不符合要求时返回false，否则返回true
*/
static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
{
    /* 判断基因是否合法 */
    if (!is_gene_legal(gene1, gene2))
        return false;

    /* 若基因合法则对其进行编码 */
    unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
    unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
    
    /* 组合基因片段 */
    *gene_code = (gene1_code << 11) | gene2_code;

    return true;
}
 
2.3.2、解码
 
解码是编码的逆过程，无需赘述，程序如下：
 
/*
    基因解码
    gene_code   输入型参数，基因编码
    gene1       输出型参数，解码后的基因段1
    gene2       输出型参数，解码后的基因段2

    返回值：当输入的基因编码不符合要求时返回false，否则返回true
*/
static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
{
    /* 判断基因编码是否合法 */
    if (!is_gene_code_legal(gene_code))
        return false;

    /* 若基因编码合法则对其进行解码 */
    unsigned int gene1_code = GET_GENE1_CODE(gene_code);
    unsigned int gene2_code = GET_GENE2_CODE(gene_code);

    *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
    *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;

    return true;
}
 
2.3.3、计算适应度
 
适应度函数也称评价函数，通常用于区分群体中个体好坏的标准。适应度高的，也就是优秀的个体有更大的几率参与繁衍，遗传自己的基因。一般的，适应度函数根据目标函数来确定，有时候直接将目标函数值作为适应度。这里，考虑到待求解的多峰函数，尖峰分布密集而且峰的直径很窄，这不利于遗传算法的收敛，因此本文不直接将多峰函数值作为适应度，而是利用对数函数将多峰函数进行平缓，并将平缓后的函数值作为目标函数。具体做法是，将多峰函数进行两次求对数，因此，多峰函数与适应度的关系可如下表示：
 
 用MATLAB做出适应度函数图像如下：
 
 对比前文中的图不难看出，图像得到了有效的平缓，同时不同峰之间也保持着一定的高低之别。值得一提的是，这里更主要的是给出优化遗传算法的一个思路，即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换，读者不妨思考一下，就本题而言有没有什么非常好的适应度函数。
 
据上文所述，适应度求值函数如下：
 
/*
    多峰函数：z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
    适 应 度：log(log(z))
    约    束：-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
    精    度：精确到千分位
*/
double get_fitness(const double x, const double y)
{
    return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
}
 
2.3.4、选择算子
 
本文的选择算法采用了非常常用的“轮盘赌算法”，赌盘算法的原理非常简单明了。创建赌盘时，我们将种群中所有个体的适应度求和，不妨将得到的结果称为总和适应度。然后，将每个个体的适应度除以总和适应度，然后将得到的商逐个累加，每加一次就得到赌盘的一个边界，累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理：
 
 由上文所述，赌盘创建函数可如下编写：
 
/*
    创建赌盘
    ga      遗传算法器指针
*/
static void create_roulette(GA *ga)
{
    /* 计算赌盘中的概率 */
    ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;

    for (int num = 1; num < ga->population_num - 1; num++)
    {
        ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
    }

    ga->roulette[ga->population_num - 1] = 1.0;
}
 
再回到选择算子，选择算子需要赌盘作为基础，其运行时，会产生一个0到1的随机数，然后在赌盘中找到该数所在的区间，这个区间对应的个体即为被选中的个体。因此，适应度越高的个体被选中的几率越大，这是合理的。当然，也存在较小的概率选出适应度较低的个体，为了避免这种情况，本文引入了竞争机制，即一次选择的过程选出2个个体，再取其中适应度较高的那个个体，具体的程序如下：
 
/*
    基因选择函数
    ga      遗传算法器指针
    返回值：返回使用轮盘赌的方式选出的个体(编号)
    说  明：选择策略为轮盘赌+随机竞争
*/
static unsigned int select(GA *ga)
{
    unsigned int index1 = 0, index2 = 0;

    /* 产生一个[0.0, 1.0]之间的浮点数 */
    double selector1 = rand() * 1.0 / RAND_MAX;
    double selector2 = rand() * 1.0 / RAND_MAX;

    /* 找出被选中的个体的索引 */
    for (; selector1 > ga->roulette[index1]; index1++);
    for (; selector2 > ga->roulette[index2]; index2++);

    return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
}
 
2.3.5、交叉算子
 
遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因，常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法，实现过程既不复杂，也有较好的随机性，该方法可由下图示意：
 
 图中虚线指出的两个交叉点是随机产生的。具体程序如下：
 
/*
    交叉函数
    ga          遗传算法器指针
    one         输出型参数，待交叉基因
    another     输出型参数，待交叉基因
    说明：
    1.对传入的基因编码执行两点交叉操作
*/
static void cross(GA *ga, unsigned int *one, unsigned int *another)
{
    /* 1.随机产生两个交叉点的位置 */
    unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
    unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
    unsigned char min_pos = min(pos1, pos2);
    unsigned char max_pos = max(pos1, pos2);

    /* 2.截出需要交换的基因段 */
    unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
    unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
    unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));

    /* 3.执行交叉操作 */
    *one = (*one & mask) | another_gene_seg;
    *another = (*another & mask) | one_gene_seg;
}
 
2.3.6、变异算子
 
在自然界中，基因变异可以增加个体的多样性，这对于遗传算法来说是增加了个体的随机性，可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转，程序如下：
 
/*
    变异函数
    gene_code       输入型参数
    说明：
    1.对传入的基因编码执行变异操作
    2.随机选择基因编码中的一位做反转操作
*/
static void mutate(unsigned int *gene_code)
{
    unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
    *gene_code ^= mutate_bit;
}
 
2.3.7、繁殖函数及进化函数
 
遗传算法的主要算子都在上文中分析过了，下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中，这其中涉及到两个关键的函数，即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异，同时本文还采用了子代竞争策略，即父代产生的两个子代个体仅保留适应度最高的，程序如下：
 
/*
    繁殖函数
    ga       遗传算法器指针
    father   从种群中选出的父体
    mother   从种群中选出的母体
    返回值：  适应度最高的子代的基因编码
    说明： 
    1.一对父体与母体将繁殖出一对子代
    2.选择出适应性更好的子代返回
*/
static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
{
    unsigned int son1 = ga->gene_code[father];
    unsigned int son2 = ga->gene_code[mother];

    /* 1.交叉 */
    cross(ga, &son1, &son2);

    /* 2.变异 */
    mutate(&son1);
    mutate(&son2);

    /* 3.子代竞争 */
    double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
    gene_decode(son1, &son1_gene1, &son1_gene2);
    gene_decode(son2, &son2_gene1, &son2_gene2);

    return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
}
 
进化函数则实现了遗传算法的一次完整的迭代过程，根据上文给出的遗传算法流程图，不难进行如下编码：
 
/*
    进化函数
    ga      遗传算法器指针
*/
static void evolve(GA *ga)
{
    /* 1.申请暂存子代基因编码的内存 */
    unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
    
    /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
    descendants[0] = ga->gene_code[ga->best_individual];
    
    /* 3.选择合适的父体与母体 */
    unsigned int father = select(ga);
    unsigned int mother = select(ga);

    /* 4.繁殖(包含交叉与变异) */
    for (int num = 1; num < ga->population_num; num++)
        descendants[num] = inherit(ga, father, mother);

    /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
    for (int num = 0; num < ga->population_num; num++)
    {
        ga->gene_code[num] = descendants[num];
        gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
    }
    
    /* 5.更新种群适应度 */
    fit(ga);
    
    /* 6.更新赌盘 */
    create_roulette(ga);

    /* 7.释放之前申请的空间 */
    free(descendants);
}
 
3、运行结果及分析
 
至此，本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群，并进行100代迭代以求解多峰函数的最大值，一次完整的调用本文实现的遗传算法的程序如下所示：
 
/* 创建遗传算法器 */
GA *ga = create_ga(get_fitness, 100);

/* 初始化遗传算法器 */
ga->init(ga);

/*迭代100代*/
for (int i = 0; i < 100; i++)
ga->evolve(ga);

/*销毁遗传算法器*/
delete_ga(ga);
 
经多次调用测试，算法执行的结果较为稳定，所得的多峰函数最大值大多在38以上，多次运行结果中最好的解为38.849744，对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下：
 
 为验证是否找到了最优解，用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501，与本文求出的结果相差0.000356，可见本文实现的遗传算法表现还不算太差。
 
文中给出的程序比较散，这里给出完整程序的下载链接。

一、前言
       旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。
二、模拟退火法
       模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。其流程可以概括如下

随机产生一个初始访问序列，并计算响应的行程和，保存为当前最佳路径。
设置初始温度T(0)，终止温度T(min)，降温系数a。
while(T>T(min))，在当前的最优值，按照某一邻域函数，产生新的路径，并计算新路径的路径和。如果优于最优值，则更迭最优决策，如果不是，按照Metropolis法则选择是否更新。
降温，达到循环终止条件则跳出。
Metropolis法则

 


 可以避免局部陷阱


 
matlab代码

%C表示初始城市坐标
C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];
n=length(C);
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
%计算距离矩阵
for i=1:n
    for j=i:n
        if i~=j
            D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
        else
            D(i,j)=eps;      %i=j时不计算，应该为0，用eps（浮点相对精度）表示
        end
        D(j,i)=D(i,j);   %对称矩阵
    end
end
%初始化
path_best=[];
T=3000;
delta_T=0.98; %降温系数
p=randperm(n);
dist=0.0;
path_best=p;
for i=1:n-1
    dist=dist+D(p(i),p(i+1));
end
dist=dist+D(p(1),p(n));
dist_best=dist;
%降温循环过程
while(T>1e-8)
    %采用最简单的邻域取法，直接对换其中两个节点的城市
    x=ceil(n*rand());
    y=ceil(n*rand());
    while(x==y)
        x=ceil(n*rand());
        y=ceil(n*rand());
    end
    z=p(x);
    p(x)=p(y);
    p(y)=z;
    for i=1:n-1
        dist=dist+D(p(i),p(i+1));
    end
    dist=dist+D(p(1),p(n));    
    if(dist<dist_best)
        dist_best=dist;
        path_best=p;
    else
        a=exp(-(dist-dist_best)/T);
        b=rand(); 
        if(a>b)  %概率大于产生随机数时则采用
            dist_best=dist;
            path_best=p;  
        end
    end
    T=T*delta_T;
end
%画图输出结果
subplot(1,1,1) 
scatter(C(:,1),C(:,2));
hold on
plot([C(path_best(1),1),C(path_best(n),1)],[C(path_best(1),2),C(path_best(n),2)],'g')
hold on
for ii=2:n
plot([C(path_best(ii-1),1),C(path_best(ii),1)],[C(path_best(ii-1),2),C(path_best(ii),2)],'g')
hold on
end
title(['旅行商问题优化结果 :',num2str(dist_best)])

输出结果
                              
从结果可以看出启发式算法的特点，由于是经验算法，结果并不是严格意义上的最优解，因此具有一定的随机性，但只要迭代次数足够多，总可以收敛到最优解附近。
三、遗传算法
       遗传算法（GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体(individual)组成。每个个体实际上是染色体带有特征的实体。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

其主要流程如下：
初始化参数，包括种群数量，繁衍代数，变异概率，城市坐标，染色体长度等。
计算距离矩阵，生成初始种群。
当迭代次数不满足时，执行杂交循环。
杂交包括选择，交叉，变异三个过程。选择的方法有很多种，此处采用最简单的最优者生存的方法，即目标函数前60%的个体可以顺利繁衍后代。也可以采用轮盘赌的方法，所有个体均可以繁衍后代，但是目标值越优的个体被挑选的概率越大。交叉的过程是随机生成染色体长度内的两个整数值，并将选择出的两个个体的该段染色体交叉互换。变异按照一定概率进行，当生成的随机数大于变异概率时则进行变异。
更新种群，采用“精英保留”的策略。即在种群数量一定的情况下，每次总是留下目标最优的群体。继续循环直到满足跳出条件。
matlab代码如下：
%主程序部分
NUM=20;%种群大小
GEN=100;%代数
P=0.7;%变异概率
C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];%城市坐标
n=length(C);
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
%计算初始距离矩阵
for i=1:n
    for j=i:n
        if i~=j
            D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
        else
            D(i,j)=eps;      %i=j时不计算，应该为0，用eps（浮点相对精度）表示
        end
        D(j,i)=D(i,j);   %对称矩阵
    end
end
group=zeros(NUM,n);%种群
dist=zeros(NUM,1);%路径和

%生成初始种群
for i=1:NUM
    group(i,:)=randperm(n);
    for j=1:n-1
        dist(i)=dist(i)+D(group(i,j),group(i,j+1));
    end
    dist(i)=dist(i)+D(group(i,1),group(i,n));
end
res=[group,dist];
res=sortrows(res,n+1);%按路径和排序
path_best=res(1,1:n);%保存最优路径和最小路径和
dist_min=res(1,n+1);
M=floor(NUM*0.6);%0.6为适应度系数，即假设60%为适应并繁衍的种群

%执行杂交操作
for i=1:GEN         
    res=yichuan(res,M,n,D,P,NUM);
    path_best=res(1,1:n);
    dist_min=res(1,n+1);
end
%输出结果
subplot(1,1,1) 
scatter(C(:,1),C(:,2));
hold on
plot([C(path_best(1),1),C(path_best(n),1)],[C(path_best(1),2),C(path_best(n),2)],'g')
hold on
for ii=2:n
plot([C(path_best(ii-1),1),C(path_best(ii),1)],[C(path_best(ii-1),2),C(path_best(ii),2)],'g')
hold on
end
title(['旅行商问题优化结果 :',num2str(dist_min)])
遗传函数部分
function [res]=yichuan(res,M,n,D,P,NUM)
%res为储存路径和总距离的矩阵，M为适应生存的种群数，n为染色体长度，D为距离矩阵，P是变异概率，NUM为种群数
group=res(1:M,1:n);
dist=res(1:M,n+1);
list=randperm(M);%随机生成父本和母本序列
for j=1:2:M-1
    [group(list(j),:),group(list(j+1),:)]=jiaocha(group(list(j),:),group(list(j+1),:),n,P);
    dist(j)=cal_dist(group(j,:),D,n);
    dist(j+1)=cal_dist(group(j+1,:),D,n); 
end
R=zeros(2*M,n+1);
R=[res;group,dist];
R=sortrows(R,n+1);
res=R(1:NUM,:);%精英保留
end

%交叉，变异
function [r1,r2]=jiaocha(r1,r2,n,P)
    a=randperm(n,2);
    l=min(a);
    m=max(a);
    while(l==m)
        a=randperm(10,2);
        l=min(a);
        m=max(a);
    end    
    a1=r1;
    a2=r2;
    %交换中间部分，并替换重复出现的染色体
    for k=l:m
        r1(k)=a2(k);
        r2(k)=a1(k);
        x=find(a1==r1(k));
        y=find(a2==r2(k));
        r1(x)=a1(k);
        r2(y)=a2(k);
        a1=r1;
        a2=r2;
    end
    %随机数大于变异概率则变异
    if(rand()>P)
        q=randperm(n,2);
        s=r1(q(1));
        r1(q(1))=r1(q(2));
        r1(q(2))=s;
    end
    if(rand()>P)
        q=randperm(n,2);
        s=r2(q(1));
        r2(q(1))=r2(q(2));
        r2(q(2))=s;
    end
end

%计算路径和
function [dist]=cal_dist(path,Dist,n)
    dist=0;
    for k=1:n-1
        dist=dist+Dist(path(k),path(k+1));
    end
    dist=dist+Dist(path(1),path(n));
        
end
输出结果


四、蚁群算法
       最早是由Marco Dorigo等人在1991年提出，基于信息正反馈原理。蚂蚁视觉十分不发达，却能够在没有任何提示的情况下找到食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。原因是蚂蚁在寻找食物源的时候，能在其走过的路径上释放信息素，当一些路径上通过的蚂蚁越来越多，信息素也越来越多，蚂蚁选择该路径的概率也就越大。对单个蚂蚁来说，它没有找到最短路径，但对整个蚁群来说，却达到了寻找最优路径的客观效果。

其算法流程如下：

对相关参数进行初始化，包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等，以及将数据读入程序，并进行预处理：比如将城市的坐标信息转换为城市间的距离矩阵。 
随机将蚂蚁放于不同出发点，对每个蚂蚁计算其下个访问城市，直到有蚂蚁访问完所有城市。 
计算各蚂蚁经过的路径长度LkLk，记录当前迭代次数最优解，同时对路径上的信息素浓度进行更新。
判断是否达到最大迭代次数，若否，继续循环。
输出结果，并根据需要输出寻优过程中的相关指标，如运行时间、收敛迭代次数等。

代码如下：
%%第一步：变量初始化
C=[1,2;70,90;80,60;10,100;800,200;800,100;90,80;200,600;230,4;500,90];

NC_max=200;
m=18;
Alpha=1;
Beta=5;
Rho=0.5;
Q=1;
n=size(C,1);%n表示问题的规模（城市个数）
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
    for j=i:n
        if i~=j
            D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
        else
            D(i,j)=eps;      %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示
        end
        D(j,i)=D(i,j);   %对称矩阵
    end
end
Eta=1./D;          %Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);     %Tau为信息素矩阵
Tabu=zeros(m,n);   %存储并记录路径的生成
NC=1;               %迭代计数器，记录迭代次数
R_best=zeros(NC_max,n);       %各代最佳路线
L_best=inf.*ones(NC_max,1);   %各代最佳路线的长度
L_ave=zeros(NC_max,1);        %各代路线的平均长度
 
while NC<=NC_max        %停止条件之一：达到最大迭代次数，停止
%%第二步：将m只蚂蚁放到n个城市上
Randpos=[];   %随即存取
for i=1:(ceil(m/n))  %向上取整
    Randpos=[Randpos,randperm(n)];  %并成一列
end
Tabu(:,1)=(Randpos(1,1:m))';    %第一行的1到m列元素
 
%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游
for j=2:n     %所在城市不计算
    for i=1:m    
        visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问
        J=zeros(1,(n-j+1));       %待访问的城市
        P=J;                      %待访问城市的选择概率分布
        Jc=1;
        for k=1:n
            if length(find(visited==k))==0   %开始时置0，找出未访问的城市,find返回的是位置
                J(Jc)=k;
                Jc=Jc+1;                         
            end
        end
%下面计算待选城市的概率分布
        for k=1:length(J)
            P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
        end
        P=P/(sum(P));
        %按概率原则选取下一个城市
%         Pcum=cumsum(P);     %cumsum返回行和和列和，sum返回列和
%         Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线
        Select=max(P);
        Select=find(P==Select);
        to_visit=J(Select(1));
        Tabu(i,j)=to_visit;
    end
end
if NC>=2
    Tabu(1,:)=R_best(NC-1,:);
end
 
%%第四步：记录本次迭代最佳路线
L=zeros(m,1);     %开始距离为0，m*1的列向量
for i=1:m
    R=Tabu(i,:);
    for j=1:(n-1)
        L(i)=L(i)+D(R(j),R(j+1));    %原距离加上第j个城市到第j+1个城市的距离
    end
    L(i)=L(i)+D(R(1),R(n));      %一圈，回到起点
end
L_best(NC)=min(L);           %最佳距离取最小
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线
L_ave(NC)=mean(L);           %此轮迭代后的平均距离
NC=NC+1                      %迭代继续
 
 
%%第五步：更新信息素
Delta_Tau=zeros(n,n);        %开始时信息素为n*n的0矩阵
for i=1:m
    for j=1:(n-1)
        Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);          
        %此次循环在路径（i，j）上的信息素增量
    end
    Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
    %此次循环在整个路径上的信息素增量
end
Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素
Tabu=zeros(m,n);             %%直到最大迭代次数
end
%%第六步：输出结果
Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真）
Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
subplot(1,2,1)                  %绘制第一个子图形
DrawRoute(C,Shortest_Route)     %画路线图的子函数
subplot(1,2,2)                  %绘制第二个子图形
plot(L_best)
hold on                         %保持图形
plot(L_ave,'r')
title('平均距离和最短距离')     %标题
end


function DrawRoute(C,R)
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')
hold on
end
title('旅行商问题优化结果 ')
end
输出结果

遗传算法原理解析
 
遗传算法（GA）是一种元启发式自然选择的过程，属于进化算法（EA）大类。遗传算法通常是利用生物启发算子，如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。
 
 
借鉴生物进化理论，遗传算法将问题模拟成一个生物进化过程，通过遗传、交叉、突变、自然选择等操作产生下一代的解，并逐步淘汰适应度函数值低的解，增加适应度函数高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。
 
 
 
与遗传算法有关的生物学概念：
 
（1）染色体（chromosome）
 生物是由细胞组成，每一个细胞中都有一套相同的染色体。一条染色体由若干基因(gene) 组成，每个基因控制一种特定的蛋白质，从而决定生物的某种特征。所有染色体合称为基因组(genome)。基因组完全决定了一个生物个体。该个体在微观（基因）层次的表现称为基因型 (genotype)，在宏观（特征）层次的表现称为显型 (phenotype)。在简单的遗传算法中，将基因组中的若干条染色体看作一整条染色体。
 （2） 个体复制
 在复制的过程中，父母的染色体通过交叉（crossover）产生子女的染色体。染色体还可以以一定的小概率变异（mutate）。
  
 
 
遗传算法本质上是一种搜索算法，搜索算法的共同特征为：
 
首先组成一组候选解
依据某些适应性条件测算这些候选解的适应度
根据适应度保留某些候选解，放弃其他候选解
对保留的候选解进行某些操作，生成新的候选解
 

 
　　
 交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。
 交叉前：
 00000|011100000000|10000
 11100|000001111110|00101
 交叉后：
 00000|000001111110|10000
 11100|011100000000|00101
 染色体交叉是以一定的概率发生的，这个概率记为Pc 。
 变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm 。
 变异前：
 000001110000000010000
 变异后：
 000001110000100010000
 适应度函数 ( Fitness Function )：用于评价某个染色体的适应度，用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如：0-1背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。
 
 
遗传算法伪代码
 
 
基本遗传算法伪代码
/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
 
do
{ 
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
　　　　if ( random ( 0 , 1 ) < Pm )
　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )
 
 
遗传算法优化方法：
 
 
（1）精英主义(Elitist Strategy)选择：是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。
 （2）插入操作：可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。
 
 
遗传算法实例
 

 这里选用参考3中的实例：
 计算函数
  
 
 
 
 
 的最小值，其中每个变量的取值区间都是[-1, +1]。
 
 
 首先，确定适应度的函数：
 
 
 
 
function y = my_fitness(population)
% population是随机数[0,1]矩阵，下面的操作改变范围为[-1,1]
population = 2 * (population - 0.5); 
y = sum(population.^2, 2); % 行的平方和
 遗传算法实现：
 
 
 
function [best_fitness, elite, generation, last_generation] = my_ga( ...
    number_of_variables, ...    % 求解问题的参数个数
    fitness_function, ...       % 自定义适应度函数名
    population_size, ...        % 种群规模（每一代个体数目）
    parent_number, ...          % 每一代中保持不变的数目（除了变异）
    mutation_rate, ...          % 变异概率
    maximal_generation, ...     % 最大演化代数
    minimal_cost ...            % 最小目标值（函数值越小，则适应度越高）
)

% 累加概率
% 假设 parent_number = 10
% 分子 parent_number:-1:1 用于生成一个数列
% 分母 sum(parent_number:-1:1) 是一个求和结果（一个数）
% 分子 10     9     8     7     6     5     4     3     2     1
% 分母 10+9+...+1=55
% 相除 0.1818    0.1636    0.1455    0.1273    0.1091    0.0909    0.0727    0.0545    0.0364    0.0182
% 累加(cumsum) 0.1818    0.3455    0.4909    0.6182    0.7273    0.8182    0.8909    0.9455    0.9818    1.0000
% 运算结果可以看出: 累加概率函数是一个从0到1增长得越来越慢的函数
cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); % 1个长度为parent_number的数列
best_fitness = ones(maximal_generation, 1);% 记录每一代最佳适应度,先初始化为1
elite = zeros(maximal_generation, number_of_variables);% 记录每一代的最优解，初始化为0

% 子女数量=种群数量 - 父母数量（父母即每一代中不发生改变的个体）
child_number = population_size - parent_number; % 每一代子女的数目

% population_size 对应矩阵的行，每一行表示1个个体，行数=个体数（种群数量）
% number_of_variables 对应矩阵的列，列数=参数个数（个体特征由这些参数表示）
population = rand(population_size, number_of_variables);% 初始化种群
last_generation = 0; % 记录跳出循环时的代数

for generation = 1 : maximal_generation % 演化循环开始
    
    % feval把数据带入到一个定义好的函数句柄中计算
    % 把population矩阵带入fitness_function函数计算
    cost = feval(fitness_function, population); % 计算所有个体的适应度（population_size*1的矩阵）

    % index记录排序后每个值原来的行数
    [cost, index] = sort(cost); % 将适应度函数值从小到大排序

    % index(1:parent_number) 
    % 前parent_number个cost较小的个体在种群population中的行数
    % 选出这部分(parent_number个)个体作为父母，其实parent_number对应交叉概率
    population = population(index(1:parent_number), :); % 先保留一部分较优的个体
    % population矩阵是不断变化的
    % cost在经过前面的sort排序后，矩阵已经改变为升序的
    % cost(1)即为本代的最佳适应度
    best_fitness(generation) = cost(1); % 记录本代的最佳适应度

    % population矩阵第一行为本代的最优解（精英）
    elite(generation, :) = population(1, :); % 记录本代的最优解（精英）

    % 若本代的最优解已足够好，则停止演化
    if best_fitness(generation) < minimal_cost; 
        last_generation = generation;
        break; 
    end
    
    % 交叉变异产生新的种群，染色体交叉开始
    for child = 1:2:child_number % 步长为2是因为每一次交叉会产生2个孩子
        
        % cumulative_probabilities 长度为 parent_number
        % 从中随机选择2个父母出来  (child+parent_number)
        mother = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的母亲
        father = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的父亲
        
        % ceil：向上取整
        % rand 生成一个随机数
        % 即随机选择了一列，这一列的值交换
        crossover_point = ceil(rand*number_of_variables); % 随机地确定一个染色体交叉点
        
        % 假如crossover_point=3, number_of_variables=5
        % mask1 = 1     1     1     0     0
        % mask2 = 0     0     0     1     1
        mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];
        mask2 = not(mask1);
        
        % 获取分开的4段染色体
        mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分
        mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分
        
        father_1 = mask1 .* population(father, :); % 父亲染色体的前部分
        father_2 = mask2 .* population(father, :); % 父亲染色体的后部分
        
        % 得到下一代
        population(parent_number + child, :) = mother_1 + father_2; % 一个孩子
        population(parent_number+child+1, :) = mother_2 + father_1; % 另一个孩子
        
    end % 染色体交叉结束
    
    
    % 染色体变异开始，变异种群
    mutation_population = population(2:population_size, :); % 精英不参与变异，从2开始    
    number_of_elements = (population_size - 1) * number_of_variables; % 全部基因数目
    number_of_mutations = ceil(number_of_elements * mutation_rate); % 变异的基因数目（基因总数*变异率）
    
    % rand(1, number_of_mutations) 生成number_of_mutations个随机数(范围0-1)组成的矩阵(1*number_of_mutations)
    % 数乘后，矩阵每个元素表示发生改变的基因的位置（元素在矩阵中的一维坐标）
    mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 确定要变异的基因
    
    % 被选中的基因都被一个随机数替代，完成变异
    mutation_population(mutation_points) = rand(1, number_of_mutations); % 对选中的基因进行变异操作
    population(2:population_size, :) = mutation_population; % 发生变异之后的种群
    % 染色体变异结束
end % 演化循环结束
 函数测试：
 
 
 
clc,clear all,close all;

% 调用 my_ga 进行计算
% 求解问题的参数个数         10
% 自定义适应度函数名         my_fitness
% 种群规模                  100
% 每一代中保持不变的数目     50 (即交叉率0.5)
% 变异概率                  0.1 (1/10的个体发生变异)
% 最大演化代数              10000 10000代
% 最小目标值                1.0e-6 个体适应度函数值 < 0.000001结束
[best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);

% 输出后10行
disp(last_generation); 
i_begin = last_generation - 9;
disp(best_fitness(i_begin:last_generation,:));
% disp(best_fitness(9990:10000,:));
% disp(elite(9990:10000,:))
% 不要写成这样，因为GA常常在中间就跳出循环了

% 将elite值转化为问题范围内
my_elite = elite(i_begin:last_generation,:);
my_elite = 2 * (my_elite - 0.5);
disp(my_elite);

% 最佳适应度的演化情况
figure
loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
xlabel('Generation','fontsize',15);
ylabel('Best Fitness','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

% 最优解的演化情况
figure
semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
xlabel('Generation','fontsize',15);
ylabel('Best Solution','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

 
 
 
 
 
 
 
参考：
 http://blog.jobbole.com/110913/
 http://blog.csdn.net/dazhong159/article/details/7908531
 
 
http://blog.sciencenet.cn/blog-3102863-1029280.html
 
https://github.com/Shuai-Xie/genetic-algorithm
 
 
https://github.com/yanshengjia/artificial-intelligence/tree/master/genetic-algorithm-for-functional-maximum-problem/src
 
 

 

其他文章：
 
通过0-1背包问题看穷举法、贪心算法、启发式算法（JAVA)
 
模拟退火(SA)算法实例介绍（JAVA)
 
遗传算法（GA）实例介绍（JAVA)
 
CPLEX求解器入门案例
 
cplex的下载、安装、IDE编程及相关问题解决
 
 
用最简单的0-1背包问题（1-0 knapsack problem）来说明穷举法、贪心算法、启发式算法。
 
0-1背包问题简述：
 
 
 
有一个背包，背包能装的物品重量是有限的，只能装C kg的物品。
 现在有N个物品，每个物品都有自己的重量w和价值v。
 现在要你决策：选哪些物品装进背包，才能使得不超过背包容量情况下，装的物品价值最大？
 
 
一、穷举法
 
穷举法是一种暴力求解方式。首先穷举所以可能的情况，也就是找到解空间，然后遍历解空间找到最好的方案。
 通过穷举生成解空间（n个物品）：对每个物品要么选择（1），要么不选择（0）；生成一个长度为n的数组，数组的每个元素表示每个物品，元素的值为0或1，得到的每个数组就是一种可能的解；所有的数组放一起就是解空间。n个物品，解空间中有2^n种可能（每个物品要么选择要么不选择）。
 
1.1.代码实现
 
算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223
 
package com.wuxiaolong.algorithm.knapsackProblem;

import java.util.ArrayList;
import java.util.List;

/**
 * 整数规划中的 0-1背包问题
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        // 启动
        exhaustAlgorithm();
    }

    /**
     * 1.穷举法
     *  
     */
    public static void  exhaustAlgorithm(){

        // 1.算例定义：背包限制重量100  有4个物品 每个物品的重量和价值
        double knapsackLimit = 100;
        int goodsNum = 4;
        double[] weights = {18,42,88,3};
        double[] values ={141,136,192,223};

        // 2.根据商品数量生成解空间(递归+回溯)
        List<List<Integer>> solutionSpace = getSolutionSpace(goodsNum);

        // 3.评价每个解
        double maxVal = 0;
        List<Integer> solve = null;
        for(int i=0; i<solutionSpace.size();i++){
            List<Integer> curr = solutionSpace.get(i);
            double w = 0;
            double v = 0;
            for(int j=0; j<curr.size(); j++){
                if(curr.get(j) == 1){
                    w += weights[j];
                    v += values[j];
                }
            }

            // 满足约束条件
            if(w<=knapsackLimit){
                if(v>=maxVal){
                    maxVal = v;
                    solve = curr;
                }
            }
        }

        // 4.输出最优解
        System.out.println("最大价值："+ maxVal + "  最优方案："+solve);
    }

    /**
     * 穷举解空间中的所有解
     */
    public static List<List<Integer>> getSolutionSpace(int goodsNum){

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        // 递归的层数 相当于每个物品就是一层for
        Integer index = 1;
        Integer length = goodsNum;

        // 递归
        dfs(result,path,length,index);

        System.out.println("解空间元素个数: "+result.size());
        System.out.println("解空间详情：");
        result.forEach(System.out::println);

        return result;
    }

    public static void dfs(List<List<Integer>> result,List<Integer> path, int length, int index){

        // 终止条件
        if(index>length){
            // 获取一个解
            result.add(new ArrayList<>(path));
            return;
        }

        // 每个物品有两种选择方式 1：选   0：不选
        for(int i=0; i<2; i++){
            path.add(i);
            dfs(result,path,length,index+1);
            // 回溯
            path.remove(index-1);
        }
    }
}
 
1.2.运行结果
 
 
上面的背包问题，通过穷举法我们找到了最优解；上面有4个商品时，解空间有24=16种可能。当商品数为50个时，解空间中需要验证的解就是250=1125899906842624种可能，假如一秒钟可以计算10亿次，需要1125899秒=312小时。这在时间生活生产中是不能接受的。可见穷举法求解时间随问题规模增长而呈爆炸式增长，这也是穷举法的最大问题。
 
1.3.总结
 
穷举法的特点：
 
通过比较解空间中的所有解（可行的和不可行的），穷举法一定能找到问题的最优解。穷举法简单粗暴，结果还是最优。
在问题规模较小时，是一种比较好的解决问题的方式
当问题规模过大时，求解所消耗的资源是不能接受的，需要寻找其他方式解决问题。
 
二、贪心算法
 
贪心算法是将一个问题差分成多个子问题，找到每个子问题的最优解就找到了全局的最优解。比如需要分别从10个箱子中取一张钞票（假如每个箱子中都有各种面额的钞票），要求取得的钞票加起来总面额最高，这时就可以从每个箱子中取最大面额的钞票就会使整个金额最大。对于某些问题贪心是一种很好的方式，但是对于某些情况，贪心就不能满足要求。贪心是一种目光短浅的做法，因为它只关注当前的最优性，而对于最后总体会变成什么样子就不管不顾了。
 
2.1.代码实现
 
使用上面相同的算例，用贪心算法编码：
 
算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223
 
package com.wuxiaolong.algorithm.knapsackProblem;

import java.util.*;

/**
 * 整数规划中的 0-1背包问题
 *
 */
public class KnapsackProblem1 {

    public static void main(String[] args) {
        greedyAlgorithm();
    }

    /**
     * 1.贪心算法
     *   每次拿满足条件的价值最大的商品，如果不满足条件就拿价值次大的商品，依次内推.....
     *
     */
    public static void  greedyAlgorithm(){

        // 1.算例定义：背包限制 10个物品 每个物品的重量和价值
        double knapsackLimt = 100;
        int goodsNum = 4;
        double[] weights = {18,42,88,3};
        double[] values ={141,136,192,223};

        // 2.商品信息放入item对象
        List<Item> goodsList = new ArrayList<>();
        for(int i=0; i<values.length; i++){
            Item item = new Item(weights[i],values[i],i);
            goodsList.add(item);
        }

        // 3.将商品列表按照价值重量比排序
        Collections.sort(goodsList, new Comparator<Item>(){
            @Override
            public int compare(Item o1, Item o2) {
                return o2.getValWghtRate().compareTo(o1.getValWghtRate());
            }
        });
        System.out.println("按照价值重量比排序后的结果：{}"+goodsList);

        // 4.每次找满足条件的最大的商品，每个商品找一次
        List<Item> selectedGoods = new ArrayList<>();
        double currSumWeight = 0;
        double maxVal = 0;
        for(int i=0; i<goodsList.size(); i++){
            Item tmp = goodsList.get(i);

            if(currSumWeight + tmp.getWeight() < knapsackLimt){
                selectedGoods.add(tmp);
                currSumWeight += tmp.getWeight();
                tmp.setSelect(1);
                maxVal += tmp.getValue();
            }
        }

        // 5.打印最优结果
        int[] solve = new int[goodsList.size()];
        for (Item t : selectedGoods){
            solve[t.getOrder()] = t.getSelect();
        }
        System.out.println("最大价值："+ maxVal + "  最优方案："+ Arrays.toString(solve));
    }


    public static class Item{
        // 重量
        private Double weight;
        // 价值
        private Double value;
        // 价值重量比
        private Double valWghtRate;
        // 商品原来的顺序
        private Integer order;
        // 是否选择该商品 默认不选
        private Integer select = 0;

        public Item(){}

        public Item(Double weight,Double value,Integer order){
            this.weight = weight;
            this.value = value;
            this.order = order;
            this.valWghtRate = value/weight;
        }

        public Double getWeight() {
            return weight;
        }

        public void setWeight(Double weight) {
            this.weight = weight;
        }

        public Double getValue() {
            return value;
        }

        public void setValue(Double value) {
            this.value = value;
        }

        public Double getValWghtRate() {
            return valWghtRate;
        }

        public void setValWghtRate(Double valWghtRate) {
            this.valWghtRate = valWghtRate;
        }

        public Integer getOrder() {
            return order;
        }

        public void setOrder(Integer order) {
            this.order = order;
        }

        public Integer getSelect() {
            return select;
        }

        public void setSelect(Integer select) {
            this.select = select;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "weight=" + weight +
                    ", value=" + value +
                    ", order=" + order +
                    '}';
        }
    }
}

 
2.2.运行结果
 
 
这里可以看出，在这个算例中，找到了最优解，而且和穷举法结果一样。这是不是就意味着贪心算法就可以解决最优化问题呢？答案是否定的。贪心算法不仅仅是简单的局部最优这么简单，他最终的结果跟贪心的方式是密切相关的。比如上面我们每次选择的是价值重量比最大的物品，也可以每次拿价值最大的物品，这样得到的结果就会不一样。
 
因为上面的代码的时间复杂度是O(n)，在问题规模变大时，贪心算法计算消耗的时间就会远远小于穷举法，是平缓的线性增长。贪心算法其实就是一个“构造”解的过程而已，相比较于枚举法而言，贪心是没有“搜索”这一过程的，他只是按照一定的方式，将解给构造起来而已。
 
对于TSP问题的Greedy算法解决，其思想是随机生成第一个城市，加入cityList，然后从剩下城市中，依次找离cityList最后一个城市最近的放进cityList中。
 
如果决策的每一步之间是独立的，通过设计出优秀的贪心策略，可以取得比较不错的结果，这个时候可以选择贪心算法。这种情况通常可以将整个问题的各个步骤的决策重新分解为一个一个独立的子问题，各个子问题互不影响，贪心获得子问题的最优，组合起来就是全局最优解。
 
决策的每一步之间是不是独立的，选择贪心方式求解，不可能出现求出的解不能用的情况。
 
2.3.总结
 
贪心算法的特点：
 
贪心算法通过“构造”的方式求解，没有“搜索”的过程，算法的时间复杂度是O(n)，随问题规模的增长是平缓的线性增长。
决策的每一步之间是独立的，通过设计出优秀的贪心策略，可以取得比较不错的结果，有时候甚至能找到最优解。
决策的每一步之间是不是独立的，选择贪心方式求解的结果可能会有很大问题。
 
三、启发式算法
 
问题规模大时，穷举法时间太长没法用；问题复杂时，贪心算法的结果质量太差；所以就需要找到一条既能够得到一个比较优质的解，又能将求解资源控制在一定范围内的算法。这就出现了启发式算法。
 
启发式算法就是在一个合理的求解资源范围内（合理的时间，合理的内存开销等）求得一个较为满意的解。该解毫无疑问，是要优于或等于贪心解，有可能达到枚举法求得的最优解。
 
3.1.全局搜索和局部搜索
 
在介绍启发式算法之前，先了解一下全局搜索和局部搜索。
 
算法的本质就是在解空间（解空间中包括可行解和不可行解）中搜索出最优解。穷举法是构建出解所有的情况，然后验证每种情况，从而找到最优解，所以穷举法需要遍历整个解空间，是全局搜索的过程，当问题规模增大时，其解空间就会变得很大很大，全局搜索的效率就会很低，需要的时间复杂度或空间复杂度是无法接受的。
 
全局搜索不能接受时，可以使用局部搜索：不完全遍历解空间，只挑一部分出来进行遍历，就可以大大降低搜索需要的资源消耗，同时也可能在局部中找到最优解，或者还不错的一个解。
 
通常考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。**局部搜索是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。**局部搜索能力和全局搜索能力，缺一不可。向最优解的导向，对于任何智能算法的性能都是很重要的。
 
3.2.盲目搜索和启发式搜索
 
按照预定的策略进行解的搜索，在搜索过程中获取的中间信息不用于改进后续的搜索策略，称之为盲目搜索（比如穷举法、蒙塔卡罗模拟）。反之，如果利用了中间的信息来改进搜索策略则称之为启发式搜索（比如爬山算法、模拟退火算法、粒子群算法、遗传算法、蚁群算法等）。
 
关于“启发式”，可以简单总结为一下亮点：
 
任何有助于找到问题最优解，但不能保证找到最优解的方法均是启发式方法；
有助于加速求解过程和找到较优解方法是启发式方法。
 
盲目搜索的执行过程大致是：首先，随机生成很多组解，然后验证这些解是否满足约束条件，若满足则将其保存到一个“可行集”中，然后计算这个可行集内的每个解对应的目标函数值，最后找到最值即可。穷举法和蒙塔卡罗模拟的区别是解空间的生成：蒙塔卡罗模拟解空间中的解是随机生成的，穷举法可能是按照一定的规则生成的（比如步长）。
 
3.3.启发式搜索
 
启发式算法目前主要包括邻域搜索和群体仿生两大类。群体仿生类比如遗传算法、模拟退火算法、粒子群算法、蚁群算法等，这些智能搜索也叫元启发式搜索。
 
具体相关的算法，在其他文章中单独介绍介绍过。