精华内容
下载资源
问答
  • 2021-04-18 05:42:13

    function varargout = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res)

    %TSP_GA Traveling Salesman Problem (TSP) Genetic Algorithm (GA)

    % Finds a (near) optimal solution to the TSP by setting up a GA to search

    % for the shortest route (least distance for the salesman to travel to

    % each city exactly once and return to the starting city)

    %

    % Summary:

    % 1. A single salesman travels to each of the cities and completes the

    % route by returning to the city he started from

    % 2. Each city is visited by the salesman exactly once

    %

    % Input:

    % XY (float) is an Nx2 matrix of city locations, where N is the number of cities

    % DMAT (float) is an NxN matrix of point to point distances/costs

    % POP_SIZE (scalar integer) is the size of the population (should be divisible by 4)

    % NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run

    % SHOW_PROG (scalar logical) shows the GA progress if true

    % SHOW_RES (scalar logical) shows the GA results if true

    %

    % Output:

    % OPT_RTE (integer array) is the best route found by the algorithm

    % MIN_DIST (scalar float) is the cost of the best route

    %

    % 2D Example:

    % n = 50;

    % xy = 10*rand(n,2);

    % pop_size = 60;

    % num_iter = 1e4;

    % show_prog = 1;

    % show_res = 1;

    % a = meshgrid(1:n);

    % dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);

    % [opt_rte,min_dist] = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res);

    %

    % 3D Example:

    % n = 50;

    % xyz = 10*rand(n,3);

    % pop_size = 60;

    % num_iter = 1e4;

    % show_prog = 1;

    % show_res = 1;

    % a = meshgrid(1:n);

    % dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);

    % [opt_rte,min_dist] = tsp_ga(xyz,dmat,pop_size,num_iter,show_prog,show_res);

    %

    % See also: mtsp_ga, tsp_nn, tspo_ga, tspof_ga, tspofs_ga, distmat

    %

    % Author: Joseph Kirk

    % Email: jdkirk630@gmail.com

    % Release: 2.2

    % Release Date: 6/2/09

    % Process Inputs and Initialize Defaults

    nargs = 6;

    for k = nargin:nargs-1

    switch k

    case 0

    xy = 10*rand(50,2);

    case 1

    N = size(xy,1);

    a = meshgrid(1:N);

    dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);

    case 2

    pop_size = 100;

    case 3

    num_iter = 1e4;

    case 4

    show_prog = 1;

    case 5

    show_res = 1;

    otherwise

    end

    end

    % Verify Inputs

    [N,dims] = size(xy);

    [nr,nc] = size(dmat);

    if N ~= nr || N ~= nc

    error('Invalid XY or DMAT inputs!')

    end

    n = N;

    % Sanity Checks

    pop_size = 4*ceil(pop_size/4);

    num_iter = max(1,round(real(num_iter(1))));

    show_prog = logical(show_prog(1));

    show_res = logical(show_res(1));

    % Initialize the Population

    pop = zeros(pop_size,n);

    for k = 1:pop_size

    pop(k,:) = randperm(n);

    end

    % Run the GA

    global_min = Inf;

    total_dist = zeros(1,pop_size);

    dist_history = zeros(1,num_iter);

    tmp_pop = zeros(4,n);

    new_pop = zeros(pop_size,n);

    if show_prog

    pfig = figure('Name','TSP_GA | Current Best Solution','Numbertitle','off');

    end

    for iter = 1:num_iter

    % Evaluate Each Population Member (Calculate Total Distance)

    for p = 1:pop_size

    d = dmat(pop(p,n),pop(p,1)); % Closed Path

    for k = 2:n

    d = d + dmat(pop(p,k-1),pop(p,k));

    end

    total_dist(p) = d;

    end

    % Find the Best Route in the Population

    [min_dist,index] = min(total_dist);

    dist_history(iter) = min_dist;

    if min_dist < global_min

    global_min = min_dist;

    opt_rte = pop(index,:);

    if show_prog

    % Plot the Best Route

    figure(pfig);

    rte = opt_rte([1:n 1]);

    if dims == 3, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'r.-');

    else plot(xy(rte,1),xy(rte,2),'r.-'); end

    title(sprintf('Total Distance = %1.4f, Iteration = %d',min_dist,iter));

    end

    end

    % Genetic Algorithm Operators

    rand_pair = randperm(pop_size);

    for p = 4:4:pop_size

    rtes = pop(rand_pair(p-3:p),:);

    dists = total_dist(rand_pair(p-3:p));

    [ignore,idx] = min(dists);

    best_of_4_rte = rtes(idx,:);

    ins_pts = sort(ceil(n*rand(1,2)));

    I = ins_pts(1);

    J = ins_pts(2);

    for k = 1:4 % Mutate the Best to get Three New Routes

    tmp_pop(k,:) = best_of_4_rte;

    switch k

    case 2 % Flip

    tmp_pop(k,I:J) = fliplr(tmp_pop(k,I:J));

    case 3 % Swap

    tmp_pop(k,[I J]) = tmp_pop(k,[J I]);

    case 4 % Slide

    tmp_pop(k,I:J) = tmp_pop(k,[I+1:J I]);

    otherwise % Do Nothing

    end

    end

    new_pop(p-3:p,:) = tmp_pop;

    end

    pop = new_pop;

    end

    if show_res

    % Plots the GA Results

    figure('Name','TSP_GA | Results','Numbertitle','off');

    subplot(2,2,1);

    if dims == 3, plot3(xy(:,1),xy(:,2),xy(:,3),'k.');

    else plot(xy(:,1),xy(:,2),'k.'); end

    title('City Locations');

    subplot(2,2,2);

    imagesc(dmat(opt_rte,opt_rte));

    title('Distance Matrix');

    subplot(2,2,3);

    rte = opt_rte([1:n 1]);

    if dims == 3, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'r.-');

    else plot(xy(rte,1),xy(rte,2),'r.-'); end

    title(sprintf('Total Distance = %1.4f',min_dist));

    subplot(2,2,4);

    plot(dist_history,'b','LineWidth',2);

    title('Best Solution History');

    set(gca,'XLim',[0 num_iter+1],'YLim',[0 1.1*max([1 dist_history])]);

    end

    % Return Outputs

    if nargout

    varargout{1} = opt_rte;

    varargout{2} = min_dist;

    end

    更多相关内容
  • tsp_iter1.c

    2020-01-07 10:54:32
    旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题,在运筹学和理论...
  • tsp_iter2.c

    2020-01-07 10:57:35
    旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题,在运筹学和理论...
  • TSP_旅行商问题 - 遗传算法(四)

    万次阅读 多人点赞 2017-01-22 12:54:12
    本文修改日志:2017.01.22:整理并发布第一版... 一、前言 【旅行商问题】旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该...

    本文修改日志:

    2017.01.22:整理并发布第一版博文;

    2018.05.01:修改源代码170行(添加float),double RateVariation = float(rand()%100)/100; 

    一、前言

        【旅行商问题】旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法模拟退火法蚁群算法禁忌搜索算法、贪婪算法神经网络等。【百度百科】


    旅行商求解系列:

    -------------------------------------------------------------------------------------------------

    (1)TSP_旅行商问题- 蛮力法( 深度遍历优先算法DFS )
    (2)TSP_旅行商问题- 动态规划
    (3)TSP_旅行商问题- 模拟退火算法
    (4)TSP_旅行商问题- 遗传算法
    (5)TSP_旅行商问题- 粒子群算法
    (6)TSP_旅行商问题- 神经网络

    -------------------------------------------------------------------------------------------------

    二、本文概要

           本文基于遗传算法的思想解决旅行商问题,满足了时间复杂度可接受,而且又不会陷入局部最优。本文首先简要介绍了遗传算法(GA)以及核心思想,此外,还给出具体实现程序的具体数据结构(最后提供本文的完整的代码以及整个工程的资源)。然后重点介绍了遗传算法的总体设计以及算法的详略流程,还结合代码重点介绍了遗传算法的几大核心部分,包括“选择(父代)”,“交叉”,“个体变异”,“更新种群(自然选择或者精英保留法)”等。最后根据实验代码给出实验结果,并对本文做出总结。

    三、遗传算法

    1. 遗传算法简介(GA)

           模拟进化计算(Simulated Evolutionary Computation) 是近二十年来信息科学、人工智能与计算机科学的一大研究领域,由此所派生的求解优化问题的仿生类算法(遗传算法、演化策略、进化程序),由于其鲜明的生物背景、新颖的设计原理、独特的分析方法和成功的应用实践,正日益形成全局搜索与多目标优化理论的一个崭新分支
           遗传算法(GeneticAlgorithm ,GA )是通过模拟生物进化过程来完成优化搜索的,由美国J. Holland 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点,使其成为21 世纪智能计算核心技术之一。进入80 年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的话题。

    2. 用遗传算法解决旅行商问题(GA solve  the TSP problem)

           目前针对TSP问题有许多种解法,较为常用的算法有神经网络法、列表寻优法、二叉树描述法、模拟退火法和遗传算法等等。遗传算法是近几年发展起来的一种崭新的全局优化算法,它借用了生物遗传学的观点,通过选择、遗传、变异和免疫等作用机制,使每个个体的适应性提高。由于其全局搜索的特性,遗传算法在解决TSP问题中有着其他算法所没有的优势。提出的TSP问题包括31个城市的编号和各自的位置。本文基于遗传算法解决TSP问题并进行编程和问题求解。

    3. 遗传算法核心思想

           模拟进化算法的核心思想源于这样的基本认识:体现在“优胜劣汰”这一自然规律的生物进化过程本身是一个自然的、并行发生的、鲁棒的优化过程,这一优化过程的目标是对环境的适应性(fitness),而生物种群通过生物体的遗传、变异来达到优化(亦即进化)之目的,对生物进化的这种优化观点早在六十年代就引起J.H.Holland、I.Recenberg及L.J.Fogel等计算智能学者的特别兴趣,并相继创立了现在被称之为遗传算法(genetic algorithms)、演化策略(evolution strategies)和进化程序(evolutionary programming)的模拟进化算法。
    • 参数的设置,确定个体的编码方式(二进制或者其他)
    • 初始随机解的生成
    • 选择算子:选择父代的策略(轮盘赌策略)
    • 繁殖:交叉两个父代并产生新个体(TSP问题的编码,需要解决路径冲突问题,即保证每个城市有且仅遍历一次)
    • 变异:对新个体进行变异操作
    • 竞争(更新种群):精英保留策略或者自然选择

    4. 本文使用的数据结构以及GA相关参数

    	#define CITY_NUM 150				// TSP_城市个数
    	#define GROUP_NUM 30				// 群体规模
    	#define SON_NUM 32				// 产生儿子的个数	SON_NUM = GROUP_NUM + 2
    
    	const double P_INHERIATANCE = 0.01;	// 变异概率
    	const double P_COPULATION = 0.8;	// 杂交概率
    	const int ITERATION_NUM = 1500;		// 遗传次数(迭代次数)
    	const double MAX_INT = 9999999.0;
    
    	typedef struct{
    		int vex_num, arc_num;			// 顶点数 边数
    		int vexs[CITY_NUM];			// 顶点向量
    		double arcs[CITY_NUM][CITY_NUM];	// 邻接矩阵
    	}Graph;
    
    	typedef struct{
    		double length_path;
    		int path[CITY_NUM];
    		double P_Reproduction;
    	}TSP_solution;

    四、程序流程

    1. 遗传算法总体设计

    • 步骤一、初始化参数;
    • 步骤二、随机产生一组初始个体构成的初始种群,并评价每一个个体的适配值(路径长度决定);
    • 步骤三、判断算法的收敛准则是否满足(此处为迭代次数)。若满足输出搜索结果;否则执行[4-8]步骤;
    • 步骤四、执行选择操作(随机选择两个种群个体),使用【轮盘赌选择】思想,每次按照概率大小随机返回当前群体中的某个个体的下标;
    • 步骤五、按杂交概率const double P_COPULATION = 0.8;执行交叉操作;
    • 步骤六、对子群Son_solution[]进行变异处理,产生随机数RateVariation,小于变异概率P_INHERIATANCE时,进行变异处理(随机交换两个城市的位置);
    • 步骤七、更新Son_solution[]的路程和概率Calc_Probablity(G, total_length);
    • 步骤八、采用“父子混合选择”更新群体(精英保留策略);
    • 步骤九、返回步骤(2)判断是否进行下一次迭代;
    说明:
    • 本算法的结束准则是根据指定了的迭代次数,当算法达到迭代次数时,算法结束,输出当前的最优解;
    • 在根据适配值计算并选择的时候,记录下来的当前最优值,在变异后加入跟新的群体,保证新的迭代循环中TSP解越来越好(不会变差);
    • 在选择的一种操作是拿最优的K个替换最差的K个子个体,本例是按适配值选择,并使群体数目变少,当每次变异操作后,产生随机路径补充群体是群体数目不变,再次循环,一定程度上防止因初始群体的选择问题而陷入局部最优。

    2. 总体流程图


                  遗传算法总体流程设计

    3. 详细流程图


    遗传算法详细流程图(来源于百度图片)

    五、程序开发 - 遗传算法解决TSP问题

    1. 随机生成初始种群:

    void InitialGroup(Graph G){
    
    	cout<<"----------------------【遗传算法参数】-----------------------"<<endl;
    	cout<<"【城市个数】 CITY_NUM ="<< CITY_NUM <<endl;
    	cout<<"【群体规模】 GROUP_NUM = "<< GROUP_NUM <<endl;
    	cout<<"【子代规模】 SON_NUM = "<< SON_NUM <<endl;
    	cout<<"【变异概率】 P_INHERIATANCE = "<< P_INHERIATANCE <<endl;
    	cout<<"【杂交概率】 P_COPULATION = "<< P_COPULATION <<endl;
    	cout<<"【迭代次数】 ITERATION_NUM = "<< ITERATION_NUM <<endl;
    
    	double total_length = 0.0;
    	for(int i = 0;i < GROUP_NUM; i++){
    		for (int j = 0;j < G.vex_num; j++)
    		{
    			TSP_Groups[i].path[j] = G.vexs[j];
    		}
    		random_shuffle(TSP_Groups[i].path + 1, TSP_Groups[i].path + G.vex_num);
    		if (Check_path(G, TSP_Groups[i]))
    		{
    			TSP_Groups[i].length_path = CalculateLength(G, TSP_Groups[i]);
    			total_length += TSP_Groups[i].length_path;
    		}else{
    			cout<<"【error!城市路径产生重复城市!】"<<endl;
    			TSP_Groups[i].length_path = MAX_INT;
    			TSP_Groups[i].P_Reproduction = 0;
    		}
    	}
    
    	Calc_Probablity(G, total_length);
    	TSP_Evaluate(G);
    }

    2. 遗传算法函数:

    void TSP_Evolution(Graph G){
    	/* */
    	int iter = 0;
    	while(iter < ITERATION_NUM){
    		// cout<<"***********************【第次"<<(iter + 1)<<"迭代】*************************"<<endl;
    
    		// 1. 选择
    		int Father_index = Evo_Select(G);
    		int Mother_index = Evo_Select(G);
    
    		while (Mother_index == Father_index)
    		{
    			// 防止Father和Mother都是同一个个体 -> 自交( 父母为同一个个体时, 母亲重新选择, 直到父母为不同的个体为止 )
    			cout<<"Warning!【Father_index = Mother_index】"<<endl;
    			Mother_index = Evo_Select(G);
    		}
    
    		// TSP_Groups[]为当前总群
    		TSP_solution Father = TSP_Groups[Father_index];
    		TSP_solution Mother = TSP_Groups[Mother_index];
    
    		// 2. 交叉, 存储在全局变脸 Son_solution[] 数组 - 通过M次杂交, 产生2M个新个体, 2M >= GROUP_NUM
    		int M = GROUP_NUM - GROUP_NUM/2;
    		Length_SonSoliton = 0;	// 遗传产生的个体个数, 置零重新累加
    		while(M){
    			double Is_COPULATION = ((rand()%100 + 0.0) / 100);
    			if (Is_COPULATION > P_COPULATION)
    			{
    				// cout<<"[ 这两个染色体不进行杂交 ]Is_COPULATION = "<<Is_COPULATION<<endl;
    			}else{
    				// 杂交, 将结果存储于遗传个体总群,全局变量Son_solution[]
    				Evo_Cross(G, Father, Mother);
    				M--;
    			}
    		}
    
    		// 3. 变异:针对 Son_solution[]
    		double total_length = 0.0;	// 更新新个体的概率
    
    		for (int IndexVariation = 0;IndexVariation < Length_SonSoliton; IndexVariation++)
    		{
    			double RateVariation = float(rand()%100) / 100;
    			// 产生的随机数小于变异概率 则该个体进行变异
    			if (RateVariation < P_INHERIATANCE)
    			{
    				Evo_Variation(G, IndexVariation);
    			}
    
    			// 经过变异处理后 判断是否满足TSP路径条件
    			if (!Check_path(G, Son_solution[IndexVariation]))
    			{
    				cout<<"【Error! 路径有重复!】"<<endl;
    			}
    
    			// 产生新个体, 计算新路径和新概率
    			Son_solution[IndexVariation].length_path = CalculateLength(G, Son_solution[IndexVariation]);
    			total_length += Son_solution[IndexVariation].length_path;
    		}
    
    		Calc_Probablity(G, total_length);
    
    		// 4. 更新群体
    		// 参与对象:父代 + 遗传的子代
    		Evo_UpdateGroup(G);
    
    		iter++;
    	}
    }

    3. 选择算子:

    // 选择
    /*
    	输入:当前总群
    	输出:按照一个评价, 随机从当前总群筛选出杂交对象, 本程序每次返回一个个体
    	选择方案:比例选择规则, [轮盘赌选择]
    	机制:反映在对父代种群中每一个体所赋予的允许繁殖概率及其从2M个中间个体中如何选择子代种群的机制上!
    */
    /*
    	[轮盘赌选择] -  轮盘赌选择是从染色体群体中选择一些成员的方法,被选中的机率和它们的适应性分数成比例,染色体的适应性分数愈高,被选中的概率也愈多.
    	1. 随机产生一个概率 selection_P 
    	2. [概率分布函数]声明变量 distribution_P = 0, 对于每个个体, 依次累加个体的概率到distribution_P上, 判断当前随机概率selection_P是否小于distribution_P, 若是则中该染色体, 结束循环
    
    */
    int Evo_Select(Graph G){
    	double selection_P = ((rand()%100 + 0.0) / 100);
    	// cout<<"selection_P = "<<selection_P<<endl;
    
    	double distribution_P = 0.0;
    	for (int i = 0; i < GROUP_NUM; i++)
    	{
    		distribution_P += TSP_Groups[i].P_Reproduction;
    		if (selection_P < distribution_P)
    		{
    			return i;
    		}
    	}
    	cout<<"【ERROR!】Evo_Select() 轮盘赌选择有误..."<<endl;
    	return 0;
    }

    4. 繁殖(交叉操作):

    // 交叉
    /*
    	输入:[TSP_Father , TSP_Mother]两个个体作为父母, 进行杂交
    	输出:通过杂交产生新个体(遗传算法产生2个新个体, 演化算法产生1个新个体)
    	杂交方案:[父子混合选择][自然选择 - 父母不参与竞争]
    	-- [演化策略]所使用的杂交算子是从两个个体生成一个个体的操作
    	-- [遗传算法]生成两个新个体。常见的“中间杂交”(intermediate crossover)及“随机杂交”(random crossover)等!
    */
    /*
    	TSP_杂交具体方法:
    	1. 随机选取两个交叉点i和j,记为 Father_Cross 和 Mother_Cross
    	2. 将两交叉点中间的基因段互换
    	3. 分别对Father和Mother的路径进行冲突处理:
    		-- 以Father为例, 保持Father_Cross基因段不变, 基因段以外的部分与Father_Cross基因段冲突的城市, 用Father_Cross和Mother_Cross对应的位置去互换, 直到没有冲突.
    		-- 冲突城市的确定: Father_Cross 和 Mother_Cross去补集,存放于数组 Conflict[] 中.
    */
    void Evo_Cross(Graph G, TSP_solution TSP_Father, TSP_solution TSP_Mother){
    	// 杂交过程:随机产生杂交的位置, 保证 IndexCross_i < IndexCross_j【全局变量】
    	IndexCross_i = rand() % (CITY_NUM - 1) + 1;	// 不能取到起始城市
    	IndexCross_j = rand() % (CITY_NUM - 1) + 1;	//
    	if (IndexCross_i > IndexCross_j)
    	{
    		int temp = IndexCross_i;
    		IndexCross_i = IndexCross_j;
    		IndexCross_j = temp;
    	}
    	if (IndexCross_j == CITY_NUM || IndexCross_i == 0)
    	{
    		cout<<"[ 杂交过程的随机数产生有问题... ]"<<endl;
    	}
    
    	// 杂交基因段
    	int Father_Cross[CITY_NUM];	// 父亲遗传基因段
    	int Mother_Cross[CITY_NUM];	// 母亲遗传基因段
    	int Length_Cross = 0;		// 杂交的个数
    	for (int i = IndexCross_i;i <= IndexCross_j; i++)
    	{
    		Father_Cross[Length_Cross] = TSP_Father.path[i];
    		Mother_Cross[Length_Cross] = TSP_Mother.path[i];
    		Length_Cross++;
    	}
    
    	// 开始杂交 - 处理 TSP_Father:找到Father_Cross[]中会产生冲突的城市
    	int *Conflict_Father;		// 存储冲突的位置
    	int *Conflict_Mother;
    	int Length_Conflict = 0;	// 冲突的个数
    	Conflict_Father = Get_Conflict(Father_Cross, Mother_Cross, Length_Cross, Length_Conflict);
    	Conflict_Mother = Get_Conflict(Mother_Cross, Father_Cross, Length_Cross, Length_Conflict);
    
    	// Father and Mother 交换基因段
    	int city_temp;
    	for (int i = IndexCross_i; i <= IndexCross_j; i++)
    	{
    		city_temp = TSP_Father.path[i];
    		TSP_Father.path[i] = TSP_Mother.path[i];
    		TSP_Mother.path[i] = city_temp;
    	}
    
    	// 开始杂交 - 处理 TSP_Mother, 其中Length_Conflict会在函数Get_Conflict()中改变并保存
    	TSP_solution Descendant_ONE = Handle_Conflict(G, TSP_Father, Conflict_Father, Conflict_Mother, Length_Conflict);	// 解决 TSP_Father 的冲突
    	TSP_solution Descendant_TWO = Handle_Conflict(G, TSP_Mother, Conflict_Mother, Conflict_Father, Length_Conflict);	// 解决 TSP_Mother 的冲突
    
    	Son_solution[Length_SonSoliton++] = Descendant_ONE;
    	Son_solution[Length_SonSoliton++] = Descendant_TWO;
    }

    5. 个体变异:

    // 变异
    /*
    	输入:杂交得到的所有个体(大于总群规模)
    	输出:通过变异策略, 以一定的变异概率(确定变异个数)随机选择个体进行变异
    	变异策略:随机交换染色体的片段, TSP - 随机交换两个城市的位置
    */
    void Evo_Variation(Graph G, int Index_Variation){
    	// 随机产生两个随机数表示两个城市的位置, 并进行位置交换
    	int City_i = (rand() % (CITY_NUM - 1)) + 1;	// [1, CITY_NUM - 1]起始城市不变异
    	int City_j = (rand() % (CITY_NUM - 1)) + 1;	// 
    
    	while(City_i == City_j){
    		City_j = (rand() % (CITY_NUM - 1)) + 1;
    	}
    
    	// 交换城市位置 - 变异
    	int temp_City = Son_solution[Index_Variation].path[City_i];
    	Son_solution[Index_Variation].path[City_i] = Son_solution[Index_Variation].path[City_j];
    	Son_solution[Index_Variation].path[City_j] = temp_City;
    }

    6. 更新种群(精英保留策略):

    // 父代 - TSP_Groups[]
    // 子代 - Son_solution[]
    void Evo_UpdateGroup(Graph G){
    	TSP_solution tempSolution;
    	// 先对子代 - Son_solution[] 依据路径长度进行排序 - 降序[按路径从大到小]
    	for (int i = 0; i < Length_SonSoliton; i++)
    	{
    		for (int j = Length_SonSoliton - 1; j > i; j--)
    		{
    			if ( Son_solution[i].length_path > Son_solution[j].length_path )
    			{
    				tempSolution = Son_solution[i];
    				Son_solution[i] = Son_solution[j];
    				Son_solution[j] = tempSolution;
    			}
    		}
    	}
    
    	// 更新
    	for (int i = 0; i < Length_SonSoliton; i++)	// 子代 - 按路径从大到小排序
    	{
    		for (int j = 0; j < GROUP_NUM; j++)	// 父代
    		{
    			if ( Son_solution[i].length_path < TSP_Groups[j].length_path )
    			{
    				TSP_Groups[j] = Son_solution[i];	// 种群更新
    				break;
    			}
    		}
    	}
    
    	TSP_Evaluate(G);
    }

    7. 以概率的形式计算个体优先级(路径越短概率越高):

    // 处理对象:每次新产生的群体, 计算每个个体的概率
    // 问题:解决TSP问题, 路径越短概率应该越高
    // 方案:对于当前总群, 将所有个体路径取倒数, 然后乘以该总群的总路径得到大于1的值, 然后进行归一化, 取得概率
    // 归一化:累加当前所有大于1的个体的伪概率, 得到TempTotal_P, 每个概率再分别除以 TempTotal_P 进行归一化
    void Calc_Probablity(Graph G, double total_length){
    	double TempTotal_P = 0.0;
    
    	for (int i = 0; i < GROUP_NUM ;i++)
    	{
    		TSP_Groups[i].P_Reproduction = (1.0 / TSP_Groups[i].length_path ) * total_length;
    		TempTotal_P += TSP_Groups[i].P_Reproduction;
    	}
    
    	for (int i = 0;i < GROUP_NUM; i++)
    	{
    		TSP_Groups[i].P_Reproduction = TSP_Groups[i].P_Reproduction / TempTotal_P;
    	}
    }

    8. 评价函数:

    /*  
    	// TSP - 评价函数
    	// 输入:当前总群 TSP_Groups[] - 包括 每个个体的路径和所需的长度
    	// 输出:当前总群中, 最优的个体:bestSolution
    	// 评价方法:路径最短的为最优
    */
    void TSP_Evaluate(Graph G){
    	TSP_solution bsetSolution;
    	bsetSolution = TSP_Groups[0];
    	for (int i = 1; i < GROUP_NUM; i++)
    	{
    		if (bsetSolution.length_path > TSP_Groups[i].length_path)
    		{
    			bsetSolution = TSP_Groups[i];
    		}
    	}
    }

    9. 处理冲突:

    TSP_solution Handle_Conflict(Graph G, TSP_solution ConflictSolution, int *Detection_Conflict, int *Model_Conflict, int Length_Conflict){
    	/*
    	cout<<"[ Handle_Conflict ]"<<endl<<"Detection_Conflict = ";
    	for (int i = 0;i < Length_Conflict; i++)
    	{
    		cout<<Detection_Conflict[i]<<" ";
    	}
    	cout<<endl<<"Model_Conflict = ";
    	for (int i = 0;i < Length_Conflict; i++)
    	{
    		cout<<Model_Conflict[i]<<" ";
    	}
    	cout<<endl;
    	
    
    	cout<<"【存在冲突】基因组为:";
    	for (int i = 0;i < G.vex_num;i++)
    	{
    		cout<<ConflictSolution.path[i]<<" -> ";
    	}
    	cout<<ConflictSolution.path[0]<<endl;
    	*/
    	for (int i = 0; i <= Length_Conflict; i++)
    	{
    		bool flag_FindCity = false;
    		int index = 0;
    		// [0, IndexCross_i) 寻找冲突
    		for (index = 0; index < IndexCross_i; index++)
    		{
    			if (Model_Conflict[i] == ConflictSolution.path[index])
    			{
    				flag_FindCity = true;
    				break;
    			}
    		}
    
    		// 第一段没找到, 找剩余的部分【除了交换的基因段外】
    		if (!flag_FindCity)
    		{
    			// [IndexCross_i + 1, G.vex_num) 寻找冲突
    			for (index = IndexCross_j + 1; index < G.vex_num; index++)
    			{
    				if (Model_Conflict[i] == ConflictSolution.path[index])
    				{
    					break;
    				}
    			}
    		}
    
    		// 9 8 [1 4 0 3 2] 3 2 0 --> ConflictSolution
    		// 8 7 [4 5 6 7 1] 9 6 5
    		// [0 3 2] --> Detection_Conflict
    		// [4 5 6] --> Model_Conflict
    		// 解决冲突, index 为当前i冲突的位置, 用Model_Conflict去替换.
    		// cout<<"index = "<<index<<endl;
    		ConflictSolution.path[index] = Detection_Conflict[i];
    	}
    
    	if (!Check_path(G, ConflictSolution))
    	{
    		cout<<"【error - 冲突未解决......】"<<endl;
    	}
    	// cout<<"  length_path = "<<ConflictSolution.length_path<<"    P_Reproduction = "<<ConflictSolution.P_Reproduction<<endl;
    
    	return ConflictSolution;
    }

    10. 计算程序耗时:

    #include <ctime>
    
    int main(){
    	time_t T_begin = clock();
    	// 耗时程序段
    	time_t T_end = clock();
    	double RunningTime = double(T_end - T_begin) / CLOCKS_PER_SEC;
    	cout<<endl<<"【 程序运行时间 RunningTime = " << RunningTime << " 】"<<endl;
    
    	return 0;
    }

    六、测试数据及其运行结果

    1. 测试数据:由150个城市组成,(由于数据量太大,以txt的形式共享,点击这里下载


    150个城市组合的TSP(部分数据)

    2. 运行结果及其分析:


    迭代次数为500时,程序耗时2.074秒,所得最有路径为26385.8

    迭代次数为1500时,程序耗时5.836秒,所得最有路径为18390.7(近似全局最优解)

    七、总结

    1. 总结:

    • 【GA与模拟退火算法的区别】模拟退火是采用单个个体进行优化,解的优化不易陷入局部极小,对整个解空间的覆盖不够,依赖初始参数的设置。遗传算法是一种群体性算法,具有并行性,全局搜索能力极强,局部搜索能力差。参数的选择对算法性能影响很大,并且需要对问题进行编码。
    • 【GA与模拟退火算法的相同点】两者均属于概率搜索算法。均需要平衡局部搜索与全局搜索,从而避免过早陷入局部搜索。算法的鲁棒性强,对目标函数及约束函数的形式没有严格要求,不需要其可导、连续等解析性质。两种算法均易于与其它启发式算法相融合。
    • 【应用研究领域】函数优化,组合优化,生产调度问题,自动控制,机器人智能控制,图象处理和模式识别。
    • 【展望】本文实现较简单的遗传算法,还有许多可以优化的地方,由于时间原因未进一步研究,在此不做详细介绍,有兴趣的同学可以加以改进!

    2. 遗传算法相关经验参数:

    遗传算法相关参数经验值
    总群规模M20 -- 100
    交叉概率0.4 -- 0.99
    变异概率0.0001 -- 0.1
    遗传过程的迭代次数100 -- 1000

    3. 遗传算法的优缺点:(尚待完善,后续补充)

        -- 优点:
            1)具有较强的全局搜索能力
            2)隐含并行性
            3)在计算精度要求较高时,计算时间少
        -- 缺点:
            1)易陷入局部早熟
            2)收敛性能差
            3)由连续问题归纳到组合问题求解,使得精度受到很大的影响

    八、程序源码

    1. GA.h

    #ifndef _GA_H_
    #define _GA_H_
    	#define CITY_NUM 150				// TSP_城市个数
    	#define GROUP_NUM 30				// 群体规模
    	#define SON_NUM 32				// 产生儿子的个数	SON_NUM = GROUP_NUM + 2
    
    	const double P_INHERIATANCE = 0.01;	// 变异概率
    	const double P_COPULATION = 0.8;	// 杂交概率
    	const int ITERATION_NUM = 1500;		// 遗传次数(迭代次数)
    	const double MAX_INT = 9999999.0;
    
    	typedef struct{
    		int vex_num, arc_num;			// 顶点数 边数
    		int vexs[CITY_NUM];			// 顶点向量
    		double arcs[CITY_NUM][CITY_NUM];	// 邻接矩阵
    	}Graph;
    
    	typedef struct{
    		double length_path;
    		int path[CITY_NUM];
    		double P_Reproduction;
    	}TSP_solution;
    
    	TSP_solution TSP_Groups[GROUP_NUM];		// 存储群体
    	TSP_solution Son_solution[SON_NUM];		// 存储杂交后的个体
    	int Length_SonSoliton = 0;			// 遗传产生的孩子的个数
    
    	void CreateGraph(Graph &G);
    	void InitialGroup(Graph G);
    	double CalculateLength(Graph G,TSP_solution newSolution);
    	void TSP_Evolution(Graph G);	// 模拟生物进化 - 解决TSP问题	
    
    	int Evo_Select(Graph G);		// 选择函数
    	void Evo_Cross(Graph G, TSP_solution TSP_Father, TSP_solution TSP_Mother);	// 杂交函数
    	void Evo_Variation(Graph G, int Index_Variation);	// 变异函数
    	void Evo_UpdateGroup(Graph G);
    	void TSP_Evaluate(Graph G);		// TSP - 评价函数	
    
    	int *Get_Conflict(int Conflict_Father[], int Conflict_Mother[], int Length_Cross, int &Length_Conflict);	// 返回冲突的数组
    	TSP_solution Handle_Conflict(Graph G, TSP_solution ConflictSolution, int *Detection_Conflict, int *Model_Conflict, int Length_Conflict);	// 解决冲突
    
    	void Calc_Probablity(Graph G, double total_length);	// 计算概率
    	bool Check_path(Graph G, TSP_solution CurrentSolution);
    	void Display(Graph G);
    #endif

    2. GA.cpp

    #include <iostream>
    #include <fstream>
    #include <iomanip>	// 本文用于输出对齐
    #include <stdlib.h> 
    #include <ctime>
    #include <algorithm>
    
    #include "GA.h"
    
    using namespace std;
    
    int IndexCross_i;
    int IndexCross_j;
    
    int main(){
    	time_t T_begin = clock();
    	Graph G;
    	CreateGraph(G);
    
    	srand ( unsigned ( time(0) ) );
    	InitialGroup(G);
    
    	TSP_Evolution(G);	// 遗传算法
    
    	time_t T_end = clock();
    	double RunningTime = double(T_end - T_begin) / CLOCKS_PER_SEC;
    	cout<<endl<<"【 程序运行时间 RunningTime = " << RunningTime << " 】"<<endl;
    
    
    	system("pause");
    	return 0;
    }
    
    void CreateGraph(Graph &G){
    	ifstream read_in;
    	read_in.open("L:\\Coding\\TSP_遗传算法\\TSP_遗传算法\\city_150.txt");
    	if (!read_in.is_open())
    	{
    		cout<<"文件读取失败."<<endl;
    		return;
    	}
    
    	read_in >> G.vex_num;
    	// read_in >> G.arc_num;
    	G.arc_num = 0;
    	for (int i = 0;i < G.vex_num; i++)
    	{
    		read_in >> G.vexs[i];
    	}
    	G.vexs[G.vex_num] = '\0';	// char的结束符.
    
    	for (int i = 0; i < G.vex_num;i++)
    	{
    		for (int j = 0; j < G.vex_num; j++)
    		{
    			read_in >> G.arcs[i][j];
    
    			// calculate the arc_num
    			if (G.arcs[i][j] > 0)
    			{
    				G.arc_num++;
    			}
    		}
    	}
    
    	// display
    	cout<<"无向图创建完毕,相关信息如下:"<<endl;
    	cout<<"【顶点数】 G.vex_num = "<<G.vex_num<<endl;
    	cout<<"【边数】 G.arc_num = "<<G.arc_num<<endl;
    	cout<<"【顶点向量】 vexs[max_vexNum] = ";
    	
    	for (int i = 0; i < G.vex_num; i++)
    	{
    		cout << G.vexs[i] << " ";
    	}
    }
    
    void InitialGroup(Graph G){
    
    	cout<<"----------------------【遗传算法参数】-----------------------"<<endl;
    	cout<<"【城市个数】 CITY_NUM ="<< CITY_NUM <<endl;
    	cout<<"【群体规模】 GROUP_NUM = "<< GROUP_NUM <<endl;
    	cout<<"【子代规模】 SON_NUM = "<< SON_NUM <<endl;
    	cout<<"【变异概率】 P_INHERIATANCE = "<< P_INHERIATANCE <<endl;
    	cout<<"【杂交概率】 P_COPULATION = "<< P_COPULATION <<endl;
    	cout<<"【迭代次数】 ITERATION_NUM = "<< ITERATION_NUM <<endl;
    
    	double total_length = 0.0;
    	for(int i = 0;i < GROUP_NUM; i++){
    		for (int j = 0;j < G.vex_num; j++)
    		{
    			TSP_Groups[i].path[j] = G.vexs[j];
    		}
    		random_shuffle(TSP_Groups[i].path + 1, TSP_Groups[i].path + G.vex_num);
    		if (Check_path(G, TSP_Groups[i]))
    		{
    			TSP_Groups[i].length_path = CalculateLength(G, TSP_Groups[i]);
    			total_length += TSP_Groups[i].length_path;
    		}else{
    			cout<<"【error!城市路径产生重复城市!】"<<endl;
    			TSP_Groups[i].length_path = MAX_INT;
    			TSP_Groups[i].P_Reproduction = 0;
    		}
    	}
    
    	Calc_Probablity(G, total_length);
    	TSP_Evaluate(G);
    }
    
    // 处理对象:每次新产生的群体, 计算每个个体的概率
    // 问题:解决TSP问题, 路径越短概率应该越高
    // 方案:对于当前总群, 将所有个体路径取倒数, 然后乘以该总群的总路径得到大于1的值, 然后进行归一化, 取得概率
    // 归一化:累加当前所有大于1的个体的伪概率, 得到TempTotal_P, 每个概率再分别除以 TempTotal_P 进行归一化
    void Calc_Probablity(Graph G, double total_length){
    	double TempTotal_P = 0.0;
    
    	for (int i = 0; i < GROUP_NUM ;i++)
    	{
    		TSP_Groups[i].P_Reproduction = (1.0 / TSP_Groups[i].length_path ) * total_length;
    		TempTotal_P += TSP_Groups[i].P_Reproduction;
    	}
    
    	for (int i = 0;i < GROUP_NUM; i++)
    	{
    		TSP_Groups[i].P_Reproduction = TSP_Groups[i].P_Reproduction / TempTotal_P;
    	}
    }
    
    void TSP_Evolution(Graph G){
    	/* */
    	int iter = 0;
    	while(iter < ITERATION_NUM){
    		// cout<<"***********************【第次"<<(iter + 1)<<"迭代】*************************"<<endl;
    
    		// 1. 选择
    		int Father_index = Evo_Select(G);
    		int Mother_index = Evo_Select(G);
    
    		while (Mother_index == Father_index)
    		{
    			// 防止Father和Mother都是同一个个体 -> 自交( 父母为同一个个体时, 母亲重新选择, 直到父母为不同的个体为止 )
    			// cout<<"Warning!【Father_index = Mother_index】"<<endl;
    			Mother_index = Evo_Select(G);
    		}
    
    		// TSP_Groups[]为当前总群
    		TSP_solution Father = TSP_Groups[Father_index];
    		TSP_solution Mother = TSP_Groups[Mother_index];
    
    		// 2. 交叉, 存储在全局变脸 Son_solution[] 数组 - 通过M次杂交, 产生2M个新个体, 2M >= GROUP_NUM
    		int M = GROUP_NUM - GROUP_NUM/2;
    		Length_SonSoliton = 0;	// 遗传产生的个体个数, 置零重新累加
    		while(M){
    			double Is_COPULATION = ((rand()%100 + 0.0) / 100);
    			if (Is_COPULATION > P_COPULATION)
    			{
    				// cout<<"[ 这两个染色体不进行杂交 ]Is_COPULATION = "<<Is_COPULATION<<endl;
    			}else{
    				// 杂交, 将结果存储于遗传个体总群,全局变量Son_solution[]
    				Evo_Cross(G, Father, Mother);
    				M--;
    			}
    		}
    
    		// 3. 变异:针对 Son_solution[]
    		double total_length = 0.0;	// 更新新个体的概率
    
    		for (int IndexVariation = 0;IndexVariation < Length_SonSoliton; IndexVariation++)
    		{
    			double RateVariation = float(rand()%100) / 100;
    			// 产生的随机数小于变异概率 则该个体进行变异
    			if (RateVariation < P_INHERIATANCE)
    			{
    				Evo_Variation(G, IndexVariation);
    			}
    
    			// 经过变异处理后 重新计算路径值
    			if (!Check_path(G, Son_solution[IndexVariation]))
    			{
    				cout<<"【Error! 路径有重复!】"<<endl;
    			}
    
    			// 产生新个体, 计算新路径和新概率
    			Son_solution[IndexVariation].length_path = CalculateLength(G, Son_solution[IndexVariation]);
    			total_length += Son_solution[IndexVariation].length_path;
    		}
    
    		Calc_Probablity(G, total_length);
    
    		/*
    		cout<<"【遗传产生的子代个体如下...】"<<endl;
    		for (int i = 0; i < Length_SonSoliton; i++)
    		{
    			for (int j = 0;j < G.vex_num;j++)
    			{
    				cout<<Son_solution[i].path[j]<<" -> ";
    			}
    			cout<<Son_solution[i].path[0]<<"    length_path = "<<Son_solution[i].length_path<<"    P_Reproduction = "<<Son_solution[i].P_Reproduction<<endl;
    		}
    		*/
    
    		// 4. 更新群体
    		// 参与对象:父代 + 遗传的子代
    		Evo_UpdateGroup(G);
    
    		iter++;
    	}
    }
    
    // 选择
    /*
    	输入:当前总群
    	输出:按照一个评价, 随机从当前总群筛选出杂交对象, 本程序每次返回一个个体
    	选择方案:比例选择规则, [轮盘赌选择]
    	机制:反映在对父代种群中每一个体所赋予的允许繁殖概率及其从2M个中间个体中如何选择子代种群的机制上!
    */
    /*
    	[轮盘赌选择] -  轮盘赌选择是从染色体群体中选择一些成员的方法,被选中的机率和它们的适应性分数成比例,染色体的适应性分数愈高,被选中的概率也愈多.
    	1. 随机产生一个概率 selection_P 
    	2. [概率分布函数]声明变量 distribution_P = 0, 对于每个个体, 依次累加个体的概率到distribution_P上, 判断当前随机概率selection_P是否小于distribution_P, 若是则中该染色体, 结束循环
    
    */
    int Evo_Select(Graph G){
    	double selection_P = ((rand()%100 + 0.0) / 100);
    	// cout<<"selection_P = "<<selection_P<<endl;
    
    	double distribution_P = 0.0;
    	for (int i = 0; i < GROUP_NUM; i++)
    	{
    		distribution_P += TSP_Groups[i].P_Reproduction;
    		if (selection_P < distribution_P)
    		{
    			return i;
    		}
    	}
    	cout<<"【ERROR!】Evo_Select() 轮盘赌选择有误..."<<endl;
    	return 0;
    }
    
    // 交叉
    /*
    	输入:[TSP_Father , TSP_Mother]两个个体作为父母, 进行杂交
    	输出:通过杂交产生新个体(遗传算法产生2个新个体, 演化算法产生1个新个体)
    	杂交方案:[父子混合选择][自然选择 - 父母不参与竞争]
    	-- [演化策略]所使用的杂交算子是从两个个体生成一个个体的操作
    	-- [遗传算法]生成两个新个体。常见的“中间杂交”(intermediate crossover)及“随机杂交”(random crossover)等!
    */
    /*
    	TSP_杂交具体方法:
    	1. 随机选取两个交叉点i和j,记为 Father_Cross 和 Mother_Cross
    	2. 将两交叉点中间的基因段互换
    	3. 分别对Father和Mother的路径进行冲突处理:
    		-- 以Father为例, 保持Father_Cross基因段不变, 基因段以外的部分与Father_Cross基因段冲突的城市, 用Father_Cross和Mother_Cross对应的位置去互换, 直到没有冲突.
    		-- 冲突城市的确定: Father_Cross 和 Mother_Cross去补集,存放于数组 Conflict[] 中.
    */
    void Evo_Cross(Graph G, TSP_solution TSP_Father, TSP_solution TSP_Mother){
    	// 杂交过程:随机产生杂交的位置, 保证 IndexCross_i < IndexCross_j【全局变量】
    	IndexCross_i = rand() % (CITY_NUM - 1) + 1;	// 不能取到起始城市
    	IndexCross_j = rand() % (CITY_NUM - 1) + 1;	//
    	if (IndexCross_i > IndexCross_j)
    	{
    		int temp = IndexCross_i;
    		IndexCross_i = IndexCross_j;
    		IndexCross_j = temp;
    	}
    	if (IndexCross_j == CITY_NUM || IndexCross_i == 0)
    	{
    		cout<<"[ 杂交过程的随机数产生有问题... ]"<<endl;
    	}
    
    	// 杂交基因段
    	int Father_Cross[CITY_NUM];	// 父亲遗传基因段
    	int Mother_Cross[CITY_NUM];	// 母亲遗传基因段
    	int Length_Cross = 0;		// 杂交的个数
    	for (int i = IndexCross_i;i <= IndexCross_j; i++)
    	{
    		Father_Cross[Length_Cross] = TSP_Father.path[i];
    		Mother_Cross[Length_Cross] = TSP_Mother.path[i];
    		Length_Cross++;
    	}
    
    	// 开始杂交 - 处理 TSP_Father:找到Father_Cross[]中会产生冲突的城市
    	int *Conflict_Father;		// 存储冲突的位置
    	int *Conflict_Mother;
    	int Length_Conflict = 0;	// 冲突的个数
    	Conflict_Father = Get_Conflict(Father_Cross, Mother_Cross, Length_Cross, Length_Conflict);
    	Conflict_Mother = Get_Conflict(Mother_Cross, Father_Cross, Length_Cross, Length_Conflict);
    
    	// Father and Mother 交换基因段
    	int city_temp;
    	for (int i = IndexCross_i; i <= IndexCross_j; i++)
    	{
    		city_temp = TSP_Father.path[i];
    		TSP_Father.path[i] = TSP_Mother.path[i];
    		TSP_Mother.path[i] = city_temp;
    	}
    
    	// 开始杂交 - 处理 TSP_Mother, 其中Length_Conflict会在函数Get_Conflict()中改变并保存
    	TSP_solution Descendant_ONE = Handle_Conflict(G, TSP_Father, Conflict_Father, Conflict_Mother, Length_Conflict);	// 解决 TSP_Father 的冲突
    	TSP_solution Descendant_TWO = Handle_Conflict(G, TSP_Mother, Conflict_Mother, Conflict_Father, Length_Conflict);	// 解决 TSP_Mother 的冲突
    
    	Son_solution[Length_SonSoliton++] = Descendant_ONE;
    	Son_solution[Length_SonSoliton++] = Descendant_TWO;
    }
    
    TSP_solution Handle_Conflict(Graph G, TSP_solution ConflictSolution, int *Detection_Conflict, int *Model_Conflict, int Length_Conflict){
    	for (int i = 0; i <= Length_Conflict; i++)
    	{
    		bool flag_FindCity = false;
    		int index = 0;
    		// [0, IndexCross_i) 寻找冲突
    		for (index = 0; index < IndexCross_i; index++)
    		{
    			if (Model_Conflict[i] == ConflictSolution.path[index])
    			{
    				flag_FindCity = true;
    				break;
    			}
    		}
    
    		// 第一段没找到, 找剩余的部分【除了交换的基因段外】
    		if (!flag_FindCity)
    		{
    			// [IndexCross_i + 1, G.vex_num) 寻找冲突
    			for (index = IndexCross_j + 1; index < G.vex_num; index++)
    			{
    				if (Model_Conflict[i] == ConflictSolution.path[index])
    				{
    					break;
    				}
    			}
    		}
    
    		// 9 8 [1 4 0 3 2] 3 2 0 --> ConflictSolution
    		// 8 7 [4 5 6 7 1] 9 6 5
    		// [0 3 2] --> Detection_Conflict
    		// [4 5 6] --> Model_Conflict
    		// 解决冲突, index 为当前i冲突的位置, 用Model_Conflict去替换.
    		// cout<<"index = "<<index<<endl;
    		ConflictSolution.path[index] = Detection_Conflict[i];
    	}
    
    	/*
    	cout<<endl<<"【解决冲突】基因组为:";
    	for (int i = 0;i < G.vex_num;i++)
    	{
    		cout<<ConflictSolution.path[i]<<" -> ";
    	}
    	cout<<ConflictSolution.path[0]<<endl;
    	
    	// 重新计算新路径的长度
    	// CalculateLength(G, ConflictSolution);
    	*/
    	if (!Check_path(G, ConflictSolution))
    	{
    		cout<<"【error - 冲突未解决......】"<<endl;
    	}
    	// cout<<"  length_path = "<<ConflictSolution.length_path<<"    P_Reproduction = "<<ConflictSolution.P_Reproduction<<endl;
    
    	return ConflictSolution;
    }
    
    int *Get_Conflict(int Detection_Cross[], int Model_Cross[], int Length_Cross, int &Length_Conflict){
    	// 同时存在于 Father_Cross 和 Mother_Cross 为不冲突的城市, 反之是冲突的城市.
    	// Detection_Cross[]:表示当前搜索的个体, 即找冲突的对象
    	// Model_Cross[]:	
    	// int Conflict[CITY_NUM];
    	int *Conflict = new int[CITY_NUM];
    	Length_Conflict = 0;
    	for (int i = 0; i < Length_Cross; i++)
    	{
    		bool flag_Conflict = true;	// 判断是否属于冲突
    		for (int j = 0; j < Length_Cross; j++)
    		{
    			if (Detection_Cross[i] == Model_Cross[j])
    			{
    				// 结束第二层循环
    				j = Length_Cross;
    				flag_Conflict = false;	// 该城市不属于冲突
    			}
    		}
    		if (flag_Conflict)
    		{
    			Conflict[Length_Conflict] = Detection_Cross[i];
    			Length_Conflict++;
    		}
    	}
    	return Conflict;
    }
    
    // 变异
    /*
    	输入:杂交得到的所有个体(大于总群规模)
    	输出:通过变异策略, 以一定的变异概率(确定变异个数)随机选择个体进行变异
    	变异策略:随机交换染色体的片段, TSP - 随机交换两个城市的位置
    */
    void Evo_Variation(Graph G, int Index_Variation){
    	// 随机产生两个随机数表示两个城市的位置, 并进行位置交换
    	int City_i = (rand() % (CITY_NUM - 1)) + 1;	// [1, CITY_NUM - 1]起始城市不变异
    	int City_j = (rand() % (CITY_NUM - 1)) + 1;	// 
    
    	while(City_i == City_j){
    		City_j = (rand() % (CITY_NUM - 1)) + 1;
    	}
    
    	// 交换城市位置 - 变异
    	int temp_City = Son_solution[Index_Variation].path[City_i];
    	Son_solution[Index_Variation].path[City_i] = Son_solution[Index_Variation].path[City_j];
    	Son_solution[Index_Variation].path[City_j] = temp_City;
    }
    
    // 父代 - TSP_Groups[]
    // 子代 - Son_solution[]
    void Evo_UpdateGroup(Graph G){
    	TSP_solution tempSolution;
    	// 先对子代 - Son_solution[] 依据路径长度进行排序 - 降序[按路径从大到小]
    	for (int i = 0; i < Length_SonSoliton; i++)
    	{
    		for (int j = Length_SonSoliton - 1; j > i; j--)
    		{
    			if ( Son_solution[i].length_path > Son_solution[j].length_path )
    			{
    				tempSolution = Son_solution[i];
    				Son_solution[i] = Son_solution[j];
    				Son_solution[j] = tempSolution;
    			}
    		}
    	}
    
    	/* 
    	cout<<"【冒泡排序后...】"<<endl;
    	for (int i = 0; i < Length_SonSoliton; i++)
    	{
    		cout<<"length_path = "<<Son_solution[i].length_path<<endl;
    	}
    	 */
    
    	// 更新
    	for (int i = 0; i < Length_SonSoliton; i++)	// 子代 - 按路径从大到小排序
    	{
    		for (int j = 0; j < GROUP_NUM; j++)	// 父代
    		{
    			if ( Son_solution[i].length_path < TSP_Groups[j].length_path )
    			{
    				TSP_Groups[j] = Son_solution[i];	// 种群更新
    				break;
    			}
    		}
    	}
    
    	TSP_Evaluate(G);
    }
    
    double CalculateLength(Graph G, TSP_solution newSolution){
    	double _length = 0;
    
    	for (int i = 0; i < G.vex_num - 1; i++)
    	{
    		int _startCity = newSolution.path[i] - 1;	// 路径下标是从 1 开始存储
    		int _endCity = newSolution.path[i+1] - 1;
    		if (G.arcs[_startCity][_endCity] == -1)
    		{
    			return MAX_INT;
    		}
    		else{
    			_length += G.arcs[_startCity][_endCity];
    		}
    	}
    
    	// 判断该路径是否能回到起始城市
    	if (G.arcs[newSolution.path[G.vex_num - 1]][newSolution.path[0] - 1] == -1)
    	{
    		return MAX_INT;
    	}
    	else{
    		_length += G.arcs[newSolution.path[G.vex_num - 1] - 1][newSolution.path[0] - 1];
    		// cout<<"_length = "<<_length<<endl;
    		return _length;
    	}
    }
    
    bool Check_path(Graph G, TSP_solution CurrentSolution){
    	for (int i = 0; i < G.vex_num;i++)
    	{
    		for (int j = i + 1; j < G.vex_num; j++)
    		{
    			if (CurrentSolution.path[i] == CurrentSolution.path[j])
    			{
    				return false;
    			}
    		}
    	}
    	return true;
    }
    
    /*  
    	// TSP - 评价函数
    	// 输入:当前总群 TSP_Groups[] - 包括 每个个体的路径和所需的长度
    	// 输出:当前总群中, 最优的个体:bestSolution
    	// 评价方法:路径最短的为最优
    */
    void TSP_Evaluate(Graph G){
    	TSP_solution bsetSolution;
    	bsetSolution = TSP_Groups[0];
    	for (int i = 1; i < GROUP_NUM; i++)
    	{
    		if (bsetSolution.length_path > TSP_Groups[i].length_path)
    		{
    			bsetSolution = TSP_Groups[i];
    		}
    	}
    
    	cout<<"当前最优个体 bsetSolution = ";
    	for (int i = 0;i < G.vex_num;i++)
    	{
    		cout<<bsetSolution.path[i]<<" -> ";
    	}
    	cout<<bsetSolution.path[0]<<"    length = "<<bsetSolution.length_path<<endl;
    
    }

    九、参考文献

    1. 胡妙娟,胡春,钱锋,遗传算法中选择策略的分析
    2. 本文相关代码以及数据:http://download.csdn.net/detail/houchaoqun_xmu/9740071
    3. 白话讲解遗传算法 (Genetic Algorithm):http://blog.chinaunix.net/uid-27105712-id-3886077.html
    4. Study on Fuzzy Classifier Based on Genetic Algorithm Optimization
    5. Feature Selection Based on Hybridization of Genetic Algorithm and Particle Swarm Optimization
    6. A genetic algorithm-based learning approach to understand customer satisfaction with OTA websites
    7. Boolean regulatory network reconstruction using literature based knowledge with a genetic algorithm optimization method
    展开全文
  • Python 代码库(差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法)安装pip install scikit-opt或者直接把源代码中的 sko 文件夹下载下来放本地也调用可以特性特性1:UDF(用户...

    一个封装了7种启发式算法的 Python 代码库
    (差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法)

    92cee04035009cdf5da84b40478497a4.png

    bdb0abc94e6040ab0588e9ff372692d0.gif

    d6aafb6ec0122826cd7df386c90ab43f.png

    dd6e6fab79529f1c73b2df02fe514513.png

    06a092638c11e0bdc58acd624e08ef0d.png

    d6201344a525febf7c45bc98b10b0c3f.png

    bb252666c08b6a046cbc4623d54538f4.png

    22212b23d9cd16798991ec0fe26d7d34.gif

    d5c1bcdc98866e3c4f26ec49adf88395.png

    安装

    pip install scikit-opt

    或者直接把源代码中的 sko 文件夹下载下来放本地也调用可以

    特性

    特性1:UDF(用户自定义算子)

    举例来说,你想出一种新的“选择算子”,如下
    -> Demo code:

    # step1: define your own operator:
    def selection_tournament(algorithm, tourn_size):
        FitV = algorithm.FitV
        sel_index = []
        for i in range(algorithm.size_pop):
            aspirants_index = np.random.choice(range(algorithm.size_pop), size=tourn_size)
            sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))
        algorithm.Chrom = algorithm.Chrom[sel_index, :]  # next generation
        return algorithm.Chrom

    导入包,并且创建遗传算法实例
    -> Demo code:

    import numpy as np
    from sko.GA import GA, GA_TSP
    
    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2
    ga = GA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],
            precision=[1e-7, 1e-7, 1])

    把你的算子注册到你创建好的遗传算法实例上
    -> Demo code:

    ga.register(operator_name='selection', operator=selection_tournament, tourn_size=3)

    scikit-opt 也提供了十几个算子供你调用
    -> Demo code:

    from sko.operators import ranking, selection, crossover, mutation
    
    ga.register(operator_name='ranking', operator=ranking.ranking). 
        register(operator_name='crossover', operator=crossover.crossover_2point). 
        register(operator_name='mutation', operator=mutation.mutation)

    做遗传算法运算

    -> Demo code:

    best_x, best_y = ga.run()
    print('best_x:', best_x, 'n', 'best_y:', best_y)
    现在 udf 支持遗传算法的这几个算子: crossover, mutation, selection, ranking
    Scikit-opt 也提供了十来个算子,参考这里
    提供一个面向对象风格的自定义算子的方法,供进阶用户使用:

    -> Demo code:

    class MyGA(GA):
        def selection(self, tourn_size=3):
            FitV = self.FitV
            sel_index = []
            for i in range(self.size_pop):
                aspirants_index = np.random.choice(range(self.size_pop), size=tourn_size)
                sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))
            self.Chrom = self.Chrom[sel_index, :]  # next generation
            return self.Chrom
    
        ranking = ranking.ranking
    
    
    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2
    my_ga = MyGA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],
            precision=[1e-7, 1e-7, 1])
    best_x, best_y = my_ga.run()
    print('best_x:', best_x, 'n', 'best_y:', best_y)

    特性2: GPU 加速

    GPU加速功能还比较简单,将会在 1.0.0 版本大大完善。
    有个 demo 已经可以在现版本运行了:

    特性3:断点继续运行

    例如,先跑10代,然后在此基础上再跑20代,可以这么写:

    from sko.GA import GA
    
    func = lambda x: x[0] ** 2
    ga = GA(func=func, n_dim=1)
    ga.run(10)
    ga.run(20)

    快速开始

    1. 差分进化算法

    Step1:定义你的问题,这个demo定义了有约束优化问题
    -> Demo code:

    '''
    min f(x1, x2, x3) = x1^2 + x2^2 + x3^2
    s.t.
        x1*x2 >= 1
        x1*x2 <= 5
        x2 + x3 = 1
        0 <= x1, x2, x3 <= 5
    '''
    
    
    def obj_func(p):
        x1, x2, x3 = p
        return x1 ** 2 + x2 ** 2 + x3 ** 2
    
    
    constraint_eq = [
        lambda x: 1 - x[1] - x[2]
    ]
    
    constraint_ueq = [
        lambda x: 1 - x[0] * x[1],
        lambda x: x[0] * x[1] - 5
    ]

    Step2: 做差分进化算法
    -> Demo code:

    from sko.DE import DE
    
    de = DE(func=obj_func, n_dim=3, size_pop=50, max_iter=800, lb=[0, 0, 0], ub=[5, 5, 5],
            constraint_eq=constraint_eq, constraint_ueq=constraint_ueq)
    
    best_x, best_y = de.run()
    print('best_x:', best_x, 'n', 'best_y:', best_y)

    2. 遗传算法

    第一步:定义你的问题
    -> Demo code:

    import numpy as np
    
    
    def schaffer(p):
        '''
        This function has plenty of local minimum, with strong shocks
        global minimum at (0,0) with value 0
        '''
        x1, x2 = p
        x = np.square(x1) + np.square(x2)
        return 0.5 + (np.sin(x) - 0.5) / np.square(1 + 0.001 * x)

    第二步:运行遗传算法
    -> Demo code:

    from sko.GA import GA
    
    ga = GA(func=schaffer, n_dim=2, size_pop=50, max_iter=800, lb=[-1, -1], ub=[1, 1], precision=1e-7)
    best_x, best_y = ga.run()
    print('best_x:', best_x, 'n', 'best_y:', best_y)

    第三步:用 matplotlib 画出结果
    -> Demo code:

    import pandas as pd
    import matplotlib.pyplot as plt
    
    Y_history = pd.DataFrame(ga.all_history_Y)
    fig, ax = plt.subplots(2, 1)
    ax[0].plot(Y_history.index, Y_history.values, '.', color='red')
    Y_history.min(axis=1).cummin().plot(kind='line')
    plt.show()

    06a092638c11e0bdc58acd624e08ef0d.png

    2.2 遗传算法用于旅行商问题

    GA_TSP 针对TSP问题重载了 交叉(crossover)变异(mutation) 两个算子

    第一步,定义问题。
    这里作为demo,随机生成距离矩阵. 实战中从真实数据源中读取。

    -> Demo code:

    import numpy as np
    from scipy import spatial
    import matplotlib.pyplot as plt
    
    num_points = 50
    
    points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
    distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
    
    
    def cal_total_distance(routine):
        '''The objective function. input routine, return total distance.
        cal_total_distance(np.arange(num_points))
        '''
        num_points, = routine.shape
        return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

    第二步,调用遗传算法进行求解
    -> Demo code:

    from sko.GA import GA_TSP
    
    ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
    best_points, best_distance = ga_tsp.run()

    第三步,画出结果:
    -> Demo code:

    fig, ax = plt.subplots(1, 2)
    best_points_ = np.concatenate([best_points, [best_points[0]]])
    best_points_coordinate = points_coordinate[best_points_, :]
    ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
    ax[1].plot(ga_tsp.generation_best_Y)
    plt.show()

    d6201344a525febf7c45bc98b10b0c3f.png

    3. 粒子群算法

    (PSO, Particle swarm optimization)

    3.1 带约束的粒子群算法

    第一步,定义问题
    -> Demo code:

    def demo_func(x):
        x1, x2, x3 = x
        return x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2

    第二步,做粒子群算法
    -> Demo code:

    from sko.PSO import PSO
    
    pso = PSO(func=demo_func, dim=3, pop=40, max_iter=150, lb=[0, -1, 0.5], ub=[1, 1, 1], w=0.8, c1=0.5, c2=0.5)
    pso.run()
    print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

    第三步,画出结果
    -> Demo code:

    import matplotlib.pyplot as plt
    
    plt.plot(pso.gbest_y_hist)
    plt.show()

    d5c1bcdc98866e3c4f26ec49adf88395.png

    22212b23d9cd16798991ec0fe26d7d34.gif

    3.2 不带约束的粒子群算法

    -> Demo code:

    pso = PSO(func=demo_func, dim=3)
    fitness = pso.run()
    print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

    4. 模拟退火算法

    (SA, Simulated Annealing)

    4.1 模拟退火算法用于多元函数优化

    第一步:定义问题
    -> Demo code:

    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2

    第二步,运行模拟退火算法
    -> Demo code:

    from sko.SA import SA
    
    sa = SA(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, L=300, max_stay_counter=150)
    best_x, best_y = sa.run()
    print('best_x:', best_x, 'best_y', best_y)

    d6aafb6ec0122826cd7df386c90ab43f.png

    第三步,画出结果
    -> Demo code:

    import matplotlib.pyplot as plt
    import pandas as pd
    
    plt.plot(pd.DataFrame(sa.best_y_history).cummin(axis=0))
    plt.show()

    另外,scikit-opt 还提供了三种模拟退火流派: Fast, Boltzmann, Cauchy.

    4.2 模拟退火算法解决TSP问题(旅行商问题)

    第一步,定义问题。(我猜你已经无聊了,所以不黏贴这一步了)

    第二步,调用模拟退火算法
    -> Demo code:

    from sko.SA import SA_TSP
    
    sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)
    
    best_points, best_distance = sa_tsp.run()
    print(best_points, best_distance, cal_total_distance(best_points))

    第三步,画出结果
    -> Demo code:

    from matplotlib.ticker import FormatStrFormatter
    
    fig, ax = plt.subplots(1, 2)
    
    best_points_ = np.concatenate([best_points, [best_points[0]]])
    best_points_coordinate = points_coordinate[best_points_, :]
    ax[0].plot(sa_tsp.best_y_history)
    ax[0].set_xlabel("Iteration")
    ax[0].set_ylabel("Distance")
    ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
               marker='o', markerfacecolor='b', color='c', linestyle='-')
    ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
    ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
    ax[1].set_xlabel("Longitude")
    ax[1].set_ylabel("Latitude")
    plt.show()

    92cee04035009cdf5da84b40478497a4.png

    咱还有个动画

    bdb0abc94e6040ab0588e9ff372692d0.gif

    5. 蚁群算法

    蚁群算法(ACA, Ant Colony Algorithm)解决TSP问题

    -> Demo code:

    from sko.ACA import ACA_TSP
    
    aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
                  size_pop=50, max_iter=200,
                  distance_matrix=distance_matrix)
    
    best_x, best_y = aca.run()

    dd6e6fab79529f1c73b2df02fe514513.png

    6. 免疫优化算法

    (immune algorithm, IA)
    -> Demo code:

    from sko.IA import IA_TSP
    
    ia_tsp = IA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=500, max_iter=800, prob_mut=0.2,
                    T=0.7, alpha=0.95)
    best_points, best_distance = ia_tsp.run()
    print('best routine:', best_points, 'best_distance:', best_distance)

    bb252666c08b6a046cbc4623d54538f4.png

    7. 人工鱼群算法

    人工鱼群算法(artificial fish swarm algorithm, AFSA)

    -> Demo code:

    def func(x):
        x1, x2 = x
        return 1 / x1 ** 2 + x1 ** 2 + 1 / x2 ** 2 + x2 ** 2
    
    
    from sko.AFSA import AFSA
    
    afsa = AFSA(func, n_dim=2, size_pop=50, max_iter=300,
                max_try_num=100, step=0.5, visual=0.3,
                q=0.98, delta=0.5)
    best_x, best_y = afsa.run()
    print(best_x, best_y)

    原文链接

    本文为阿里云原创内容,未经允许不得转载。

    展开全文
  • 一个封装了7种启发式算法的 Python 代码库 (差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁...sko 文件夹下载下来放本地也调用可以特性特性1:UDF(用户自定义算子)举例来说,你想出一种新的“选择算子”,如...

    一个封装了7种启发式算法的 Python 代码库 (差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法)

    image

    image

    image

    image

    image

    image

    image

    image

    安装

    
     
    
     

    pip install scikit-opt

    或者直接把源代码中的 sko 文件夹下载下来放本地也调用可以

    特性

    特性1:UDF(用户自定义算子)

    举例来说,你想出一种新的“选择算子”,如下 -> Demo code:

    
     
    
     

    step1: define your own operator: def selection_tournament(algorithm, tourn_size):

    FitV = algorithm.FitV

    sel_index = []

    for i in range(algorithm.size_pop):

    aspirants_index = np.random.choice(range(algorithm.size_pop), size=tourn_size)

    sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))

    algorithm.Chrom = algorithm.Chrom[sel_index, :] # next generation return algorithm.Chrom

    导入包,并且创建遗传算法实例 -> Demo code:

    
     
    
     

    import numpy as np

    from sko.GA import GA, GA_TSP

    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2

    ga = GA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],

    precision=[1e-7, 1e-7, 1])

    把你的算子注册到你创建好的遗传算法实例上 -> Demo code:

    
     
    
     

    ga.register(operator_name='selection', operator=selection_tournament, tourn_size=3)

    scikit-opt 也提供了十几个算子供你调用 -> Demo code:

    
     
    
     

    from sko.operators import ranking, selection, crossover, mutation

    ga.register(operator_name='ranking', operator=ranking.ranking).

    register(operator_name='crossover', operator=crossover.crossover_2point).

    register(operator_name='mutation', operator=mutation.mutation)

    做遗传算法运算

    -> Demo code:

    
     
    
     

    best_x, best_y = ga.run()

    print('best_x:', best_x, '\n', 'best_y:', best_y)

    现在 udf 支持遗传算法的这几个算子: crossover, mutation, selection, ranking Scikit-opt 也提供了十来个算子,参考这里 提供一个面向对象风格的自定义算子的方法,供进阶用户使用:

    -> Demo code:

    
     
    
     

    class MyGA(GA):

    def selection(self, tourn_size=3):

    FitV = self.FitV

    sel_index = []

    for i in range(self.size_pop):

    aspirants_index = np.random.choice(range(self.size_pop), size=tourn_size)

    sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))

    self.Chrom = self.Chrom[sel_index, :] # next generation return self.Chrom

    ranking = ranking.ranking

    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2

    my_ga = MyGA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],

    precision=[1e-7, 1e-7, 1])

    best_x, best_y = my_ga.run()

    print('best_x:', best_x, '\n', 'best_y:', best_y)

    特性2: GPU 加速

    GPU加速功能还比较简单,将会在 1.0.0 版本大大完善。 有个 demo 已经可以在现版本运行了:

    特性3:断点继续运行

    例如,先跑10代,然后在此基础上再跑20代,可以这么写:

    
     
    
     

    from sko.GA import GA

    func = lambda x: x[0] ** 2

    ga = GA(func=func, n_dim=1)

    ga.run(10)

    ga.run(20)

    快速开始

    1. 差分进化算法

    Step1:定义你的问题,这个demo定义了有约束优化问题 -> Demo code:

    
     
    
     

    '''

    min f(x1, x2, x3) = x1^2 + x2^2 + x3^2

    s.t.

    x1x2 >= 1

    x1x2 <= 5

    x2 + x3 = 1

    0 <= x1, x2, x3 <= 5

    '''

    def obj_func(p):

    x1, x2, x3 = p

    return x1 ** 2 + x2 ** 2 + x3 ** 2

    constraint_eq = [

    lambda x: 1 - x[1] - x[2]

    ]

    constraint_ueq = [

    lambda x: 1 - x[0] * x[1],

    lambda x: x[0] * x[1] - 5

    ]

    Step2: 做差分进化算法 -> Demo code:

    
     
    
     

    from sko.DE import DE

    de = DE(func=obj_func, n_dim=3, size_pop=50, max_iter=800, lb=[0, 0, 0], ub=[5, 5, 5],

    constraint_eq=constraint_eq, constraint_ueq=constraint_ueq)

    best_x, best_y = de.run()

    print('best_x:', best_x, '\n', 'best_y:', best_y)

    2. 遗传算法

    第一步:定义你的问题 -> Demo code:

    
     
    
     

    import numpy as np

    def schaffer(p):

    '''

    This function has plenty of local minimum, with strong shocks

    global minimum at (0,0) with value 0

    '''

    x1, x2 = p

    x = np.square(x1) + np.square(x2)

    return 0.5 + (np.sin(x) - 0.5) / np.square(1 + 0.001 * x)

    第二步:运行遗传算法 -> Demo code:

    
     
    
     

    from sko.GA import GA

    ga = GA(func=schaffer, n_dim=2, size_pop=50, max_iter=800, lb=[-1, -1], ub=[1, 1], precision=1e-7)

    best_x, best_y = ga.run()

    print('best_x:', best_x, '\n', 'best_y:', best_y)

    第三步:用 matplotlib 画出结果 -> Demo code:

    
     
    
     

    import pandas as pd

    import matplotlib.pyplot as plt

    Y_history = pd.DataFrame(ga.all_history_Y)

    fig, ax = plt.subplots(2, 1)

    ax[0].plot(Y_history.index, Y_history.values, '.', color='red')

    Y_history.min(axis=1).cummin().plot(kind='line')

    plt.show()

    image

    2.2 遗传算法用于旅行商问题

    GA_TSP 针对TSP问题重载了 交叉(crossover)、变异(mutation) 两个算子

    第一步,定义问题。 这里作为demo,随机生成距离矩阵. 实战中从真实数据源中读取。

    -> Demo code:

    
     
    
     

    import numpy as np

    from scipy import spatial

    import matplotlib.pyplot as plt

    num_points = 50

    points_coordinate = np.random.rand(num_points, 2) # generate coordinate of points distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')

    def cal_total_distance(routine):

    '''The objective function. input routine, return total distance.

    cal_total_distance(np.arange(num_points))

    '''

    num_points, = routine.shape

    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

    第二步,调用遗传算法进行求解 -> Demo code:

    
     
    
     

    from sko.GA import GA_TSP

    ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)

    best_points, best_distance = ga_tsp.run()

    第三步,画出结果: -> Demo code:

    
     
    
     

    fig, ax = plt.subplots(1, 2)

    best_points_ = np.concatenate([best_points, [best_points[0]]])

    best_points_coordinate = points_coordinate[best_points_, :]

    ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')

    ax[1].plot(ga_tsp.generation_best_Y)

    plt.show()

    [图片上传失败...(image-9c29c9-1597979113881)]

    3. 粒子群算法

    (PSO, Particle swarm optimization)

    3.1 带约束的粒子群算法

    第一步,定义问题 -> Demo code:

    
     
    
     

    def demo_func(x):

    x1, x2, x3 = x

    return x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2

    第二步,做粒子群算法 -> Demo code:

    
     
    
     

    from sko.PSO import PSO

    pso = PSO(func=demo_func, dim=3, pop=40, max_iter=150, lb=[0, -1, 0.5], ub=[1, 1, 1], w=0.8, c1=0.5, c2=0.5)

    pso.run()

    print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

    第三步,画出结果 -> Demo code:

    
     
    
     

    import matplotlib.pyplot as plt

    plt.plot(pso.gbest_y_hist)

    plt.show()

    image

    image

    3.2 不带约束的粒子群算法

    -> Demo code:

    
     
    
     

    pso = PSO(func=demo_func, dim=3)

    fitness = pso.run()

    print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

    4. 模拟退火算法

    (SA, Simulated Annealing)

    4.1 模拟退火算法用于多元函数优化

    第一步:定义问题 -> Demo code:

    
     
    
     

    demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2

    第二步,运行模拟退火算法 -> Demo code:

    
     
    
     

    from sko.SA import SA

    sa = SA(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, L=300, max_stay_counter=150)

    best_x, best_y = sa.run()

    print('best_x:', best_x, 'best_y', best_y)

    image

    第三步,画出结果 -> Demo code:

    
     
    
     

    import matplotlib.pyplot as plt

    import pandas as pd

    plt.plot(pd.DataFrame(sa.best_y_history).cummin(axis=0))

    plt.show()

    另外,scikit-opt 还提供了三种模拟退火流派: Fast, Boltzmann, Cauchy.

    4.2 模拟退火算法解决TSP问题(旅行商问题)

    第一步,定义问题。(我猜你已经无聊了,所以不黏贴这一步了)

    第二步,调用模拟退火算法 -> Demo code:

    
     
    
     

    from sko.SA import SA_TSP

    sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)

    best_points, best_distance = sa_tsp.run()

    print(best_points, best_distance, cal_total_distance(best_points))

    第三步,画出结果 -> Demo code:

    
     
    
     

    from matplotlib.ticker import FormatStrFormatter

    fig, ax = plt.subplots(1, 2)

    best_points_ = np.concatenate([best_points, [best_points[0]]])

    best_points_coordinate = points_coordinate[best_points_, :]

    ax[0].plot(sa_tsp.best_y_history)

    ax[0].set_xlabel("Iteration")

    ax[0].set_ylabel("Distance")

    ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],

    marker='o', markerfacecolor='b', color='c', linestyle='-')

    ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))

    ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))

    ax[1].set_xlabel("Longitude")

    ax[1].set_ylabel("Latitude")

    plt.show()

    image

    咱还有个动画

    image

    5. 蚁群算法

    蚁群算法(ACA, Ant Colony Algorithm)解决TSP问题

    -> Demo code:

    
     
    
     

    from sko.ACA import ACA_TSP

    aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,

    size_pop=50, max_iter=200,

    distance_matrix=distance_matrix)

    best_x, best_y = aca.run()

    image

    6. 免疫优化算法

    (immune algorithm, IA) -> Demo code:

    
     
    
     

    from sko.IA import IA_TSP

    ia_tsp = IA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=500, max_iter=800, prob_mut=0.2,

    T=0.7, alpha=0.95)

    best_points, best_distance = ia_tsp.run()

    print('best routine:', best_points, 'best_distance:', best_distance)

    image

    7. 人工鱼群算法

    人工鱼群算法(artificial fish swarm algorithm, AFSA)

    -> Demo code:

    
     
    
     

    def func(x):

    x1, x2 = x

    return 1 / x1 ** 2 + x1 ** 2 + 1 / x2 ** 2 + x2 ** 2

    from sko.AFSA import AFSA

    afsa = AFSA(func, n_dim=2, size_pop=50, max_iter=300,

    max_try_num=100, step=0.5, visual=0.3,

    q=0.98, delta=0.5)

    best_x, best_y = afsa.run()

    print(best_x, best_y)

    本文为阿里云原创内容,未经允许不得转载。

    展开全文
  • function varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res) nargs = 8; for k = nargin:nargs-1 switch k case 0 % xy = 10*rand(40,2); xy=[50,50;11,23;21,59;23,21;62,...
  • function varargout = mtspofs_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res) % MTSPOFS_GA Fixed Start Open Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA) % Finds...
  • github地址guofei9987/scikit-opt​github.com安装$pip install scikit-opt蚁群算法(ACA, Ant Colony Algorithm)aca = ACA_TSP(func=cal_total_distance, n_dim=8,size_pop=10, max_iter=20,distance_matrix=...
  • TSP ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1) best_points, best_distance = ga_tsp.run() # %% plot fig, ax = plt.subplots(1, 2) best_points_ = np...
  • 这里写目录标题视频学习简介TSP算法设计步骤源代码 视频学习 代码来源于清风老师授课时,使用代码,数据来源于小石老师授课资料 小石老师:https://www.bilibili.com/video/BV1Mt411x7CH?t=884&p=7 清风老师:...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼std::back_inserter(Child2));/************************************************************...for(tempIter=Child1.begin();tempIter!=Child1.end();++tempIter)cout...
  • % MTSPV_GA Variable Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA) % Finds a (near) optimal solution to a variation of the M-TSP (that has a % variable number of salesmen) by ...
  • Excel表exp12_3_1.xls中数据为: clcclear all[xdata,textdata]=xlsread('exp12_3_1.xls'); %加载20个城市的数据,数据按照表格中的位置保存在Excel文件exp12_3_1.xls中x_label=xdata(:,2); %第二列为横坐标y_label=...
  • MATLAB TSP问题

    2021-04-29 11:11:04
    %这是我写的蚁群算法解决tsp问题可以参考一下clear allclcAlpha = 1;Beta = 5;C=[565.0 575.0;25.0 185.0;345.0 750.0;945.0 685.0;845.0 655.0;880.0 660.0;25.0 230.0;525.0 1000.0;580.0 1175.0;650.0 1130.0;...
  • TSP问题的各种解法(Python)

    千次阅读 2021-12-12 11:20:00
    bestway_score() #obscore保存全局最优值 for i in range(n): obway[i] = bestway[i] f1 = obscore#f1保存当前解分值 while t > tf : for iter in range(10):# iter为等温过程迭代次数 v1 = random.randint(0,n-1) ...
  • 本文以 TSP 问题为例,通过具体代码,说明模拟退火算法的迭代过程。
  • Fixed Start/End Point Multiple Traveling Salesmen Problem - Genetic Algorithmfunction varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)% MTSPF_GA Fixed Multiple Trav...
  • #define CITYNUM 20 //城市数量 #define ANTNUM 30 //蚁群数量 #define ITER 10 //迭代最大次数 #define R 0.5 //误差大小 #define ALPHA 1 // 信息素重要程度的参数 #define BETA 4 // 启发式因子重要程度的参数 #...
  • function varargout = mtspof_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res) nargs = 8; for k = nargin:nargs-1 switch k case 0 xy = 10*rand(40,2); case 1 N = size(xy,1); a = ...
  • 鲸鱼优化算法求解TSP旅行商问题C++和Python 2022.6.2
  • 本文以 TSP 问题为例,通过具体代码,说明禁忌搜索算法的迭代过程。
  • TSP问题】基于蚁群算法求解TSP问题matlab源码 1 算法介绍 1.1 蚁群算法原理  蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而...
  • TSP、MTSP问题遗传算法详细解读及python实现

    千次阅读 热门讨论 2021-02-26 09:50:59
    写在前面 遗传算法是一种求解NPC问题的启发式算法,属于仿生进化算法族的一员。仿生进化算法是受生物行为启发而发明的智能优化算法,往往是人们发现某种生物的个体...笔者在业务中需要用到遗传算法求解TSP问题,但是网
  • 人工蜂群算法求解TSP问题

    千次阅读 2018-10-19 17:57:04
    人工蜂群算法求解TSP问题 【标签】 ABC TSP Matlab data:2018-10-19 author:怡宝2号 【总起】利用人工蜂群算法...1. 算法简介 人工蜂群算法(Artificial Bee Colony Algorithm, 简称ABC算法)是一个由蜂群行为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 779
精华内容 311
热门标签
关键字:

tsp_iter1