遗传算法的改进及其验证

２０１２年第８期　

文章编号：１００６－２４７５（２０１２）０８－００２８－０４　计算机与现代化　Ｊ１ＳＵＡＮＪ１　ＹＵ　ＸＩＡＮＤＡＩＨＵＡ　总第２０４期　

一种新型混合遗传算法及其应用　

王红　，赵培怡　

（１．山东轻工业学院财政与金融学院，山东济南２５０１００；２．山东省教育招生考试院，山东济南２５００１１）　

摘要：针对遗传算法应用的局限性，引入新的种群择优交叉运算、变异运算、遗传边界算子和相互学习过程的思想，提出　

一种新型混合遗传算法，提高了算法的收敛速度和稳定性，数值算例验证了该算法的有效性和实用性。　

关键词：遗传算法；交叉；变异；相互学习　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６￣４７５．２０１２．０８．００８　

Ａ　Ｎｅｗ　Ｈｙｂｒｉｄ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎｓ　

ＷＡＮＧ　Ｈｏｎｇ　，ＺＨＡＯ　Ｐｅｉ—ｙｉ　

（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｆｉｎａｎｃｅ，Ｓｈａｎｄｏｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｌｉｇｈｔ　Ｉｎｄｕｓｔｒｙ，Ｊｉｎａｎ　２５０１　００，Ｃｈｉｎａ；　２．Ｓｈａｎｄｏｎｇ　Ｐｒｏｖｉｎｃｉａｌ　Ａｃａｄｅｍｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ　Ｒｅｃｒｕｉｔｍｅｎｔ　ａｎｄ　Ｅｘａｍｉｎａｔｉｏｎ，Ｊｉｎａｎ　２５００１　１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｏ　ｏｖｅｒｃｏｍｅ　ｔｈｅ　ｌｉｍｉｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｂａｓｉｃ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｎｅｗ　ｈｙｂｒｉｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｔｈａｔ　ＣＯＮＩ—　ｂｉｎｅｓ　ｓｅｇ－ａｄａｐｔｉｎｇ　ｃｒｏｓｓｏｖｅｒ，ｓｔｏｃｈａｓｔｉｃ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒｓ，ｂｏｕｎｄａｒｙ　ｏｐｅｒａｔｏｒｓ　ａｎｄ　ｌｅａｒｎｉｎｇ　ｐｒｏｃｅｓｓ．Ｃｏｍｐａｒｎｇ　ｗｉｔｈ　ｔｈｅ　ｂａｓｉｃ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｂｅｔｔｅｒ　ｖｅｌｏｃｉｔｙ　ｏｆ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｈｉｇｈｅｒ　ｓｔａｂｉｌｉｔｙ，ｔｈｅ　ｎｕｍｅｒｉｃａｌ　ｅｘａｍｐｌｅｓ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ｖａｌｉｄｉｔｙ　ａｎｄ　ｅ￣ｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｎｅｗ　ｈｙｂｒｉｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｃｒｏｓｓｏｖｅｒ；ｍｕｔａｔｉｏｎ；ｌｅａｒｎｉｎｇ　ｐｒｏｃｅｓｓ　

多目标优化的遗传算法及其改进(浮点数编码)，对多个函数

进行测试

为了解决算法陷入局部最优的现象，本文主要采用以下改进算法：把

每一代种群中最优的一定数量的个体，无条件的遗传到下一代中，所以种

群的最优适应度一定会随着遗传代数的增加不断升高或者不变(达到最大

值时不再变化)，通过这种方法可以大大减小遗传算法陷入局部最优的概

率。

本文在上一篇的基础上，把单目标优化，扩展到了多目标优化，C语言

代码如下：

#includestdio.h

#includestdlib.h

#includemath.h

#includetime.h

#define M 100 --种群数量

#define N 2 --变量个数

#define PI 3.1415926

#define PC 0.8 --交叉概率

#define PM 0.4 --变异概率

#define PA 0.01 --交叉因子

#define COPYNUM 4

struct Node double Pmember[N];

double Myfitness; --Myfitness是适应度

double Myfitsum; --Myfitsum是适应度占总体适应度的百分比，

然后从第一个个体往后累加，主要用于选择操作

}Nownode[M],Nextnode[M],TempNode[COPYNUM]; --本代群体和下

一代群体,TempNode存放每一代最优的COPYNUM个个体

int nodeindex[M]; --交叉时随机配对，存放配对的群体下标

double XMIN[N]={-10,-10};--每一个参数的最小值

double XMAX[N]={10,10};--每一个参数的最大值

double fx(double *x);

int sortnode();

int copym(int n);

int copyn(int n);

int calfitsum();

基于遗传算法的路径优化方法研究及其实现

引言：

路径优化是一个常见的优化问题，它在很多领域都有广泛的应用，比如物流配送、车辆路径规划、网络路由等。而遗传算法是一种模拟生物进化过程的启发式优化算法，通过模拟自然选择和遗传机制来搜索最优解。本文将围绕基于遗传算法的路径优化方法展开研究，并提出一种实现方案。

一、遗传算法基础概念

1.1 遗传算法原理

遗传算法源于对达尔文生物进化理论的模拟，通过模拟生物的遗传、变异、适应性选择等过程来优化问题的解。

1.2 遗传算法流程

遗传算法的基本流程包括初始化种群、选择操作、交叉操作、变异操作和终止条件判断等步骤。 1.3 遗传算法参数

遗传算法的性能受到参数选择的影响，其中包括种群大小、交叉概率、变异概率等。

二、路径优化问题描述

2.1 问题定义

路径优化问题是指在给定的图中，找到一条路径使得满足一定的约束条件的情况下，路径的总长度最短。

2.2 适应度函数

为了能够将路径优化问题转化为遗传算法的优化问题，我们需要定义一个适应度函数来衡量每个个体（路径）的优劣。

三、基于遗传算法的路径优化方法

3.1 编码设计

在遗传算法中，需要将问题的解（路径）进行编码。常见的编码方式包括二进制编码、浮点数编码和排列编码等。根据问题的特点选择合适的编码方式。 3.2 初始化种群

在遗传算法中，初始化种群的质量直接影响到算法的性能。一般情况下，可以根据问题的约束条件和启发式方法来生成初始种群。

3.3 选择操作

选择操作是遗传算法中最为重要的一步，目的是根据适应度函数的值选择较优的个体。常见的选择方法包括轮盘赌选择、锦标赛选择等。

3.4 交叉操作

交叉操作是遗传算法的特点之一，通过交叉两个个体的染色体来生成新的个体。在路径优化问题中，可以采用部分映射交叉、顺序交叉等方式进行操作。

3.5 变异操作

变异操作是为了增加种群的多样性，防止算法陷入局部最优解。在路径优化问题中，可以通过交换、插入、反转等方式进行变异操作。

自适应遗传算法与邻域搜索的柔性作业车间调度方法

目录

1. 内容综述................................................2

1.1 背景介绍.............................................3

1.2 研究意义.............................................4

1.3 文献综述.............................................5

1.3.1 自适应遗传算法研究现状...........................6

1.3.2 邻域搜索方法研究现状.............................8

1.3.3 柔性作业车间调度研究现状.........................9

2. 自适应遗传算法.........................................10

2.1 遗传算法基本原理....................................12

2.2 自适应遗传算法策略..................................13

2.2.1 适应度函数设计..................................14

2.2.2 选择算子优化....................................15 2.2.3 交叉与变异算子改进..............................16

2.2.4 遗传算法参数设置................................18

3. 邻域搜索方法...........................................19