关于遗传算法研究的内容调研设计毕业论文

遗传算法产品设计论文１产品设计过程建模产品设计过程中设计活动之间的关系一般分为串行、并行和交叉三种，可以用网络图或ＤＳＭ的形式进行描述，这三种关系的网络图及相应的矩阵映射如图１所示。

图中，“＊”表示两个活动之间有信息交互，“＊”也可用数字代替，数值越大表明活动之间的信息交互越多；“０”表示两个活动之间没有信息交互。

本文使用数字ＤＳＭ来建立活动之间的信息交互耦合关系，用迭代因子表示耦合关系强度。

产品设计过程中每个设计活动都要花费时间和成本，设计活动的执行顺序对整个设计过程的时间和成本有着重大的影响。

设计迭代又增加了设计过程的复杂性，一些设计活动往往需要重复执行多次才能得到满意结果。

在实际工程应用中，返工并不是完全重复已做过的所有工作，而仅需重做其中的一部分［８］。

设计活动之间返工执行的次数用迭代因子的大小来表示，当首次执行返工时，要做该项任务的所有工作，耗时即为该任务的整个持续时间；第二次以后进行返工时，工作量为任务总工作量的一部分，耗时等于任务持续时间乘以一个小于１的正系数，该系数称为返工影响因子［９］。

因此，在考虑时间、成本和活动之间的迭代关系的同时，还要通过构建活动之间的返工影响矩阵来解决返工量变化的问题。

为了缩短设计开发周期、降低设计成本、减少设计迭代，往往需要设定设计过程多目标优化函数。

设计过程的目标优化函数一般包含成本目标、时间目标和设计活动迭代目标。

２基于遗传算法的模型优化利用遗传算法进行模型优化，采用实数编码，染色体中每个编码位表示一个活动。

假设设计活动总数为ｎ，每个编码位的取值为１、２、…、ｎ，每个整数只用一次。

算法主要步骤如下：（１）初始化群体，群体中每一条染色体对应一个活动顺序设计方案，设置种群规模。

（２）根据适应度函数计算群体中每个个体的适应度值。

（３）采用轮盘赌法来选择下一代的个体，即个体被选中并遗传到下一代群体中的概率与个体的适应度大小成正比。

（４）按交叉算子进行交叉操作，设置交叉概率。

目录1 引言 (1)2 问题描述 (2)3 基于遗传算法TSP算法 (2)3.1 基于遗传算法的TSP算法总体框架 (2)3.2算法的详细设计 (3)3.2.1 解空间的表示方式 (3)3.2.2 种群初始化 (4)3.2.3适应度函数 (4)3.2.4选择操作 (4)3.2.5交叉操作 (5)3.2.6变异操作 (6)3.2.7进化逆转操作 (6)3.3 实验结果分析 (7)4 基于模拟退火算法的TSP算法 (10)4.1 SA算法的实现过程 (10)4.2 算法流程图 (10)4.3模拟退火算法的实现过程 (10)4.4实验结果 (11)5 对两种算法的评价 (14)5.1遗传算法优缺点 (14)5.2 模拟退火算法的优缺点 (15)6结语 (15)参考文献 (17)附录： ...............................................................................................................错误!未定义书签。

廊坊师范学院本科生毕业论文论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题.本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制．利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.关键词：遗传算法；模拟退火算法；TSP；最短路径；Title：TSP Algorithm Based on Genetic Algorithm or Simulated Annealing Algorithm for Solving the Shortest Journey of 10 CitiesAbstract：TSP problem is a classic NP problem about combinatorial optimization．This article takes a travel agency looking for the shortesttrip of ten tourist cities in China－Zhuhai，Xi'an，Hangzhou，Lhasa，Beijing，Lijiang，Kunming，Chengdu，Luoyang and Weihai forinstance，and solves this problem by TSP algorithm based on geneticalgorithm and simulated annealing algorithm．The article gives theimplementations of every operator of genetic algorithm and simulatedannealing algorithm and demonstrates the architecture and theimplementation mechanism of the solving system based on MATLAB．Iprogram and operate the results by MATLAB software，and compare theresults based on genetic algorithm and simulated annealingalgorithm．And describe their advantages and disadvantages so thatchoose the most appropriate TSP algorithm to achieve the optimalsolution for the shortest path．Keywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path1 引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题[1]，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长[2]，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法．遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则[3]．遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰[4]，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解．模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性[5]，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程．其中，加温过程对应算法设定初温，等温过程对应算法的Metropolis[6]抽样过程，冷却过程对应控制参数的下降．这里能量的变化就是目标函数，要得到的最优解就是能量最低态[7]．Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis 准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱．2 问题描述本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海，根据全程路径最短为目的，制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决，寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标，下表为这十个城市的位置坐标如表2-1所示.表2-1 10个城市的位置坐标3 基于遗传算法TSP算法3.1 基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离[8]直接相连.遗传算法TSP问题的流程图如图2-1所示.N图2-1算法流程框架图3.2 算法的详细设计3.2.1 解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，因为它要求特殊的修补算子[9]来修复变化算子所产生的非法路径（即不可行路径）.给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法.它是最自然、最接近人类思维的表示法.因此对十大旅游城市按照珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海顺序依次编号为1，2，3，4，5，6，7，8，9，10，例如，下面的路径（闭合的）：5→1→2→4→3→6→7→9→8→10→5表示从城市5出发，经过1，2，4，3，6，7，9，8，10最后回到城市5的一条路径，可以自然地用一维数组来表示：（5，1，2，4，3，6，7，9，8，10）10个旅游城市的TSP问题，如果将种群规模设为200，则解空间就用二维数组来表示：Path[200][10]．3.2.2 种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销.10个城市TSP 问题，可以选择小规模的种群（例如200），种群初始化时，先产生1，2，…，10的一条规则路径，然后在这条路径中随机选两个数，将它们交换位置，这样做若干次（本文采用200次），保证这条路径变成了一条随机的路径.以这条随机路径为基础，对一些随机的位，做两两交换，这样产生了一个个体；同样地产生种群里其它的个体.3.2.3 适应度函数适应度表明个体或解的优劣性[10]，不同的问题，适应度函数的定义方式也不同，本文设12610| k ||k ||k k 为一个采用整数编码的染色体，i j k k D 为城市i k 到城市j k 的欧氏距离，则该个体的适应度为[11]：1111i j n n k k k k i fitness DD -==+∑ （1）即适应度函数为恰好走遍10个城市，在回到出发城市的总距离的倒数.优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质.求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的最优解.3.2.4 选择操作选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中，将选择算子作用于群体，从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代；个体被选中的概率与适应度值有关，适应度值越大，被选中的概率也就越大[12]，而适应度值越大的染色体越优质.本案例选择轮盘赌法，即基于适应度比例的选择策略，个体i 被选中的概率为：1ii N jj F p F==∑ （2） 其中，i F 为个体i 的适应度值；N 为种群个体数目.3.2.5 交叉操作交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性，交叉体现了信息交换的思想．利用不同映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程：（1）产生两个[1，10]区间的随机整数1r 和2r ，确定两个位置，对两个位置的中间数据进行交叉，如14r =，27r =5 1 2 4 367 98 1010 6 2 3 5 8 9 4 1 7交叉为：* 1 2 3 5 8 9 * * 1010 * 2 4 3 6 7 * 1 *（2）交叉后，对同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字（带*的位置）采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射.结果为：4 1 2 35 8 967 1010 5 2 4 3 6 7 8 1 9交叉是希望不同的个体在产生下一代时，能够结合各自的优势基因，产生更好质量的下一代.3.2.6 变异操作变异可以看作是外界对种群的影响.变异是为了引入新的因素，希望个体在外界的作用下，能够实现自我优化，生好的基因.将变异算子作用于群体.即是对群体中的个体串的某些基因位置上的基因值作变动.变异算子采用了简单的倒序变换，以10城市为例，随机的产生两个小于10的整数，对某个个体进行分割，假设14r=，27r=，将分割段倒序并放回原来的位置即可，如下数组所示：5 1 2 4 367 98 10得到的新解为：5 1 2 7 36 4 9 8 10由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的.这种简单反序可以保证后代仍然是一条合法途径.3.2.7进化逆转操作为了改善遗传算法的局部搜索能力，在选择、交叉、变异之后引进连续多次的进化逆转操作，这里的“进化”是指逆转算子的单方向性[13]，即只有经逆转后，适应度值有所提高的才接受下来，否则逆转无效.产生两个[1，10]区间内的随机整数1r和2r，确定两个位置，将其对换位置，例如14r=，27r=5 1 2 4 367 98 10进化逆转后为：5 1 2 7 36 4 9 8 10对每个个体进行交叉变异，然后代入适应度函数进行评估，x选择出适应值大的个体进行下一代交叉和变异以及进化逆转操作循环操作：判断是否满足设定的最大遗传代数MAXGEN[14]，不满足则跳入适应度值计算；否则结束遗传操作.3.3 实验结果分析1-10的十个数字按顺序为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海的编号.利用各城市坐标构成的102的矩阵及初始化随机值和DrawPath函数画出闭合路径图，为优化前的随机路线轨迹图，如图3-1所示：图3-1随机路线轨迹图图中三角标注的数字6代表起点，依次按照箭头方向遍历，最终再次回到起点6．初始种群中的一个随机值:6—>3—>7—>8—>5—>1—>2—>4—>9—>10—>6总距离：165.2494对照1-10数字编号所代表的的城市，随机路线为:丽江—>杭州—>昆明—>成都—>北京—>珠海—>西安—>拉萨—>洛阳—>威海—>丽江．优化后的最优路线图如图3-2所示：图3-2 最优路线图最优解:4—>6—>7—>1—>3—>10—>5—>9—>2—>8—>4总距离：77.1532即最优路线如下所示：拉萨—>丽江—>昆明—>珠海—>杭州—>威海—>北京—>洛阳—>西安—>成都—>拉萨此遗传算法在解决TSP问题过程中的优化迭代过程如下图3-3所示：图3-3 优化过程其中横坐标表示迭代次数，纵坐标为优化过程中路线长度.由该优化过程图可知，优化前后路径长度有了很大的改进，20代以后路径长度基本上已经保持不变了，可以认为是最优解了.总距离由原来的165.2494变为77.1532，降低为原来的46.69%，表明利用遗传算法解决TSP问题可以起到较好的作用．4 基于模拟退火算法的TSP 算法 4.1 SA 算法的实现过程 4.2 算法流程图4.3模拟退火算法的实现过程 （1）控制参数的设置需要设置的主要控制参数有降温速率q 、取初始温度0T 足够大，令T =0T ，任取初始解1S ，确定每个T 时的迭代次数，即Metropolis 链长L ，如图表4-1所示．表4-1参数设定（2）初始解对于10个城市的TSP 问题，得到的解为1~n 一个排序，其中每个数字为对应城市的编号，10个城市的TSP 问题{1，2，3，4，5，6，7，8，9，10}，则|1|2|3|4|5|6|7|8|9|10就为一个合法解，采用随机排列的方法产生一个初始解1S ． （3）解变换生成新解通过对当前解1S 进行变换，产生新路径的数组即新解，这里采用的变换是产生随机数的方法来产生将要交换的两个城市，用二邻域变换法[15]产生新的路径，即新的可行解2S .例如n=10时，产生两个[1，10]范围内的随机整数1r 和2r 确定两个位置，将其对换位置，如1r =4， 2r =75 1 2 4 367 98 10得到的新解为：5 1 2 7 36 4 9 8 10（4）Metropolis 准则若路径长度函数为()f S ，则当前解的路径为1()f S ，新解的路径为2()f S ，路径差为df =2()f S -1()f S [16]，则Metropolis 准则为[17]：1exp()P df T⎧⎪=⎨-⎪⎩ （3）若0df <，则接受2S 作为新的当前解，即1S 2S =；否则计算2S 的接受概率exp(/)df T -，即随机产生的（0，1）区间上均匀分布的随机数rand ，若exp(/)df T rand->[18]，也接受2S 作为新的当前解，1S 2S =；否则保留当前解1S ．（5）降温利用降温速率q 进行降温，即T=qT ，则T 小于结束温度，则停止迭代输出当前解1S 为最优解，结束程序，否则按衰减函数衰减T 后逐渐降低控制温度，重复Metropolis 过程，继续迭代，直至满足结束准则，求出最优解． 4.4实验结果利用各城市坐标构成的102⨯的矩阵及初始化随机值和DrawPath 函数分别画出优化前的随机路径轨迹图与优化后的最优闭合路径图，以及优化过程图．并利用计时器记录了运行结果所花费的时间．为优化前的随机路线轨迹图，如图4-2所示.图4-2随机路线轨迹图初始种群中的一个随机值:8—>1—>7—>4—>3—>6—>10—>2—>9—>5—>8总距离：149.0742优化后的最优路线轨迹图如图4-3所示.图4-3 最优路线轨迹图最优解:9—>2—>8—>4—>6—>7—>1—>3—>10—>5—>9总距离：77.1532即最优路线如下所示：洛阳—>西安—>成都—>拉萨—>丽江—>昆明—>珠海—>杭州—>威海—>北京—>洛阳本次运行的时间如下所示：Elapsed time is 12.232553 seconds.优化过程如图4-4所示:图4-4优化过程由图4-4可以看出，优化前后的路径长度得到很大的改进，由优化前的149.0742变为77.1532，变为原来的51.75%，50代以后路径长度基本上已经保持不变了，可以认为是最优解了.5 对两种算法的评价5.1遗传算法优缺点遗传算法优点：（1）对可行解表示的广泛性；（2）群体搜索特性；（3）不需要辅助信息；（4）内在启发式随机搜索特性；（5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪音的情况下，也能以很大的概率找到全局最优解；（6）遗传算法具有固有的并行性和并行计算能力；（7）遗传算法具有可扩展性，易于同别的技术混合．遗传算法缺点：（1）编码不规则或编码存在表示的不规则性；（2）单一的遗传算法编码不能全面的将优化问题的约束表示出来；（3）遗传算法通常的效率比比其他传统的优化方法低；（4）遗传算法容易出现过早收敛；（5）遗传算法对算法的精度，可信度，计算复杂性等方面，还没有有效的定量分析方法．5.2 模拟退火算法的优缺点模拟退火法优点：（1）它能够处理具有任意程度的非线性、不连续性、随机性的目标函数；（2）目标函数可以具有任意的边界条件和约束；（3）比其他线性优化方法，SA的编程工作量小，且易于实现；（4）统计上可以保证找到全局最优解．模拟退火算法缺点：（1）找到最优解需要耗费非常多的时间；（2）相对于其他一些技术对某一个具体问题的求解需要更困难的参数调整；（3）使用不当致使降温过快，导致模拟退火变为了模拟淬火（SQ），而SQ是无法从统计学上保证找到最优解的．6结语遗传算法利用自然界的“物竞天择、适者生存”的演化法则，把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体.实践证明，遗传算法在搜索优秀解的过程中模拟生物遗传，实现优中选优的过程，在解空间中快速收敛到优秀解.遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能.模拟退火算法是利用自适应启发式概率性搜索的算法，可以用以求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大的概率求得全局最优解，并且能处理不同类型的优化设计变量（离散的，连续的，混合型的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求．利用Metropolis算法适当地控制温度的下降过程，在优化问题中具有很强的竞争力，但是其优化过程效率略低于遗传算法．因此，解空间较小的情况下，遗传算法与模拟退火算法均可采用，但是解空间较大时，考虑结果运行时间，应采用遗传算法．参考文献[1]毕晓君.信息智能处理技术[M].北京:电子工业出版社.2010.[2]储理才.基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报：2001，6（01）：14-19[3]代桂平，王勇，侯亚荣.基于遗传算法的TSP问题求解算法及其系统[J].微计算机信息，2010（04）：15-16，19[4]Negnevistsky，M.顾力栩，沈晋惠译.人工智能——智能系统指南[M].北京:机械工业出版社.2010.[5]任春玉.基于混合遗传算法的ＴＳＰ问题优化研究[J].哈尔滨商业大学学报.2007.[6] Michalewicz Z. Genetic Algorithms +Data Structure=Evolution Programs.Springer-Verlag，Berlin. 2011[7] 易敬，王平，李哲. 基于遗传算法的TSP问题研究[J]. 信息技术，2006，30(7): 110-112.[8]邓辉文.离散数学[M].北京:清华大学出版社.2006.[9]刘雁兵，刘付显.基于遗传算法的TSP问题求解与仿真[J].电光与控制.2007.[10]张春霞，王蕊.基于遗传算法求解TSP问题的算法设计[J].安阳工学院学报.2007.[11]郑阿奇.MATLAB 实用教程[M].北京:电子工业出版社.2004.[12]李飞，白艳萍.用遗传算法求解旅行商问题[J].中北大学学报.2007.[13]翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报.2009.[14]Merz P.A comparison of recombination operators forthe traveling salesmanproblem[A].Proceedings of the Genetic and Evolutionary Conference.2007 [15] 周涛. 基于改进遗传算法的TSP问题研究[J]. 微电子学与计算机，2006，23(10): 104-107.[16]Jung S，Moon B R. Toward Minimal Restriction of Genetic En－coding andCrossovers for the Two-Dimensional Euclidean TSP [J].IEEE Transactions onEvolutionary Computation，2011，6 ( 12) :557~565[17]Tsai Cheng-Fa ，Tsai Chun-Wei ，Yang Tzer . A Modified Mul－tiple-Searching Method to Genetic Algorithms for Solving Travel－ing Salesman Problem[J].IEEE Transactions on Systems ，Man and Cybernetics ，2011 ，3(10) :6~12[18] Write A H. Genetic Algorithms for Real Parameter Optimization.FoundationofGeneticAlgorithms.Sanmateo，GA.2010:205-218附录：遗传算法的TSP方法代码：1 种群初始化函数InitPop的代码：%% 初始化种群%输入：% NIND：种群大小% N：个体染色体长度（这里为城市的个数）%输出：%初始种群function Chrom=InitPop(NIND,N)Chrom=zeros(NIND,N);%用于存储种群for i=1:NINDChrom(i,:)=randperm(N);%随机生成初始种群end2 种群个体的适应度函数Fitness的代码: %% 适配值函数%输入：%个体的长度（TSP的距离）%输出：%个体的适应度值function FitnV=Fitness(len)FitnV=1./len;3选择操作函数的Select的代码：%% 选择操作%输入%Chrom 种群%FitnV 适应度值%GGAP：代沟%输出%SelCh 被选择的个体function SelCh=Select(Chrom,FitnV,GGAP) NIND=size(Chrom,1);NSel=max(floor(NIND*GGAP+.5),2);ChrIx=Sus(FitnV,NSel);SelCh=Chrom(ChrIx,:);其中，函数Sus的代码为：% 输入:%FitnV 个体的适应度值%Nsel 被选择个体的数目% 输出:%NewChrIx 被选择个体的索引号function NewChrIx = Sus(FitnV,Nsel)[Nind,ans] = size(FitnV);cumfit = cumsum(FitnV);trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)');Mf = cumfit(:, ones(1, Nsel));Mt = trials(:, ones(1, Nind))';[NewChrIx, ans] = find(Mt < Mf & [ zeros(1, Nsel); Mf(1:Nind-1, :) ] <= Mt);[ans, shuf] = sort(rand(Nsel, 1));NewChrIx = NewChrIx(shuf);4 交叉操作函数Recombin的代码:%% 交叉操作% 输入%SelCh 被选择的个体%Pc 交叉概率%输出：% SelCh 交叉后的个体function SelCh=Recombin(SelCh,Pc)NSel=size(SelCh,1);for i=1:2:NSel-mod(NSel,2)if Pc>=rand %交叉概率Pc[SelCh(i,:),SelCh(i+1,:)]=intercross(SelCh(i,:),SelCh(i+1,:)); endend%输入：%a和b为两个待交叉的个体%输出：%a和b为交叉后得到的两个个体其中intercross函数代码：function [a,b]=intercross(a,b)L=length(a);r1=randsrc(1,1,[1:L]);r2=randsrc(1,1,[1:L]);if r1~=r2a0=a;b0=b;s=min([r1,r2]);e=max([r1,r2]);for i=s:ea1=a;b1=b;a(i)=b0(i);b(i)=a0(i);x=find(a==a(i));y=find(b==b(i));i1=x(x~=i);i2=y(y~=i);if ~isempty(i1)a(i1)=a1(i);endif ~isempty(i2)b(i2)=b1(i);endendend5变异操作函数Mutate的代码：%% 变异操作%输入：%SelCh 被选择的个体%Pm 变异概率%输出：% SelCh 变异后的个体function SelCh=Mutate(SelCh,Pm)[NSel,L]=size(SelCh);for i=1:NSelif Pm>=randR=randperm(L);SelCh(i,R(1:2))=SelCh(i,R(2:-1:1)); endend6进化逆转操作函数Reverse代码：%% 进化逆转函数%输入%SelCh 被选择的个体%D 个城市的距离矩阵%输出%SelCh 进化逆转后的个体function SelCh=Reverse(SelCh,D)[row,col]=size(SelCh);ObjV=PathLength(D,SelCh); %计算路径长度SelCh1=SelCh;for i=1:rowr1=randsrc(1,1,[1:col]);r2=randsrc(1,1,[1:col]);mininverse=min([r1 r2]);maxinverse=max([r1 r2]);SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:-1:mininverse); endObjV1=PathLength(D,SelCh1); %计算路径长度index=ObjV1<ObjV;SelCh(index,:)=SelCh1(index,:);7画出所给路线的轨迹图函数DrawPath的代码：%% 画路径函数%输入% Chrom 待画路径% X 各城市坐标位置function DrawPath(Chrom,X)R=[Chrom(1,:) Chrom(1,1)]; %一个随机解(个体)figure;hold onplot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)for i=1:size(X,1)text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]);endA=X(R,:);row=size(A,1);for i=2:row[arrowx,arrowy] = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));%坐标转换annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]); endhold offxlabel('横坐标')ylabel('纵坐标')title('轨迹图')box on8遗传算法的主函数代码：%遗传算法求解TSP问题(为选择操作从新设计后程序)%输入：%D 距离矩阵%NIND 为种群个数%X 参数是中国10个城市的坐标(初始给定)%MAXGEN 为停止代数，遗传到第MAXGEN代时程序停止,MAXGEN的具体取值视问题的规模和耗费的时间而定%m 为适值淘汰加速指数,最好取为1,2,3,4,不宜太大%Pc 交叉概率%Pm 变异概率%输出：%R 为最短路径%Rlength 为路径长度clearclcclose allX=[22.31 113.5834.37 108.9530.29 120.1629.66 91.1439.95 116.4126.86 100.2324.89 102.8330.59 104.0734.65 112.4637.53 122.13];D=Distanse(X); %生成距离矩阵N=size(D,1); %城市个数%% 遗传参数NIND=100; %种群大小MAXGEN=200; %最大遗传代数Pc=0.9; %交叉概率Pm=0.05; %变异概率GGAP=0.9; %代沟%% 初始化种群Chrom=InitPop(NIND,N);%% 画出随机解的路径图DrawPath(Chrom(1,:),X)titlepause(0.0001)%% 输出随机解的路径和总距离disp('初始种群中的一个随机值:')OutputPath(Chrom(1,:));Rlength=PathLength(D,Chrom(1,:));disp(['总距离：',num2str(Rlength)]);disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~')%% 优化gen=0;figure;hold on;box onxlim([0,MAXGEN])title('优化过程')xlabel('代数')ylabel('最优值')ObjV=PathLength(D,Chrom); %计算路径长度preObjV=min(ObjV);while gen<MAXGEN%% 计算适应度ObjV=PathLength(D,Chrom); %计算路径长度% fprintf('%d %1.10f\n',gen,min(ObjV))line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)preObjV=min(ObjV);FitnV=Fitness(ObjV);%% 选择SelCh=Select(Chrom,FitnV,GGAP);%% 交叉操作SelCh=Recombin(SelCh,Pc);%% 变异SelCh=Mutate(SelCh,Pm);%% 逆转操作SelCh=Reverse(SelCh,D);%% 重插入子代的新种群Chrom=Reins(Chrom,SelCh,ObjV);%% 更新迭代次数gen=gen+1 ;end%% 画出最优解的路径图ObjV=PathLength(D,Chrom); %计算路径长度[minObjV,minInd]=min(ObjV);DrawPath(Chrom(minInd(1),:),X)%% 输出最优解的路径和总距离disp('最优解:')p=OutputPath(Chrom(minInd(1),:));disp(['总距离：',num2str(ObjV(minInd(1)))]);disp('-------------------------------------------------------------')其中用到的函数如下：计算距离函数Distence代码：%% 计算两两城市之间的距离%输入 a 各城市的位置坐标%输出 D 两两城市之间的距离function D=Distanse(a)row=size(a,1);D=zeros(row,row);for i=1:rowfor j=i+1:rowD(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5; D(j,i)=D(i,j);endend输出路线函数OutputPath代码：%% 输出路径函数%输入：R 路径function p=OutputPath(R)R=[R,R(1)];N=length(R);p=num2str(R(1));for i=2:Np=[p,'—>',num2str(R(i))];enddisp(p)计算个体路线长度函数PathLength代码：%% 计算各个体的路径长度% 输入：% D 两两城市之间的距离% Chrom 个体的轨迹function len=PathLength(D,Chrom)[row,col]=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NINDp=[Chrom(i,:) Chrom(i,1)];i1=p(1:end-1);i2=p(2:end);len(i,1)=sum(D((i1-1)*col+i2));end重插入子代得到新种群的函数Reins代码：%% 重插入子代的新种群%输入：%Chrom 父代的种群%SelCh 子代种群%ObjV 父代适应度%输出% Chrom 组合父代与子代后得到的新种群function Chrom=Reins(Chrom,SelCh,ObjV)NIND=size(Chrom,1);NSel=size(SelCh,1);[TobjV,index]=sort(ObjV);Chrom=[Chrom(index(1:NIND-NSel),:);SelCh];模拟退火算法的TSP方法代码：生成新解：function S2=NewAnswer(S1)%% 输入% S1:当前解%% 输出% S2：新解N=length(S1);S2=S1;a=round(rand(1,2)*(N-1)+1);W=S2(a(1));S2(a(1))=S2(a(2));S2(a(2))=W;Metropolis准则函数function [S,R]=Metropolis(S1,S2,D,T)%% 输入% S1：当前解% S2: 新解% D: 距离矩阵（两两城市的之间的距离）% T: 当前温度%% 输出% S：下一个当前解% R：下一个当前解的路线距离%%R1=PathLength(D,S1); %计算路线长度N=length(S1); %得到城市的个数R2=PathLength(D,S2); %计算路线长度dC=R2-R1; %计算能力之差if dC<0 %如果能力降低接受新路线S=S2;R=R2;elseif exp(-dC/T)>=rand %以exp(-dC/T)概率接受新路线 S=S2;R=R2;else %不接受新路线S=S1;R=R1;Endfunction varargout = dsxy2figxy(varargin)if length(varargin{1}) == 1 && ishandle(varargin{1}) ...&& strcmp(get(varargin{1},'type'),'axes') hAx = varargin{1};varargin = varargin(2:end);elsehAx = gca;end;if length(varargin) == 1pos = varargin{1};else[x,y] = deal(varargin{:});endaxun = get(hAx,'Units');set(hAx,'Units','normalized');axpos = get(hAx,'Position');axlim = axis(hAx);axwidth = diff(axlim(1:2));axheight = diff(axlim(3:4));if exist('x','var')varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1); varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2); elsepos(1) = (pos(1) - axlim(1)) / axwidth * axpos(3) + axpos(1);pos(2) = (pos(2) - axlim(3)) / axheight * axpos(4) + axpos(2); pos(3) = pos(3) * axpos(3) / axwidth;pos(4) = pos(4) * axpos(4 )/ axheight;varargout{1} = pos;endset(hAx,'Units',axun)模拟退火算法主函数：clc;clear;close all;%%ticT0=1000; % 初始温度Tend=1e-3; % 终止温度L=500; % 各温度下的迭代次数（链长）q=0.9; %降温速率X=[22.31 113.5834.37 108.9530.29 120.1629.66 91.1439.95 116.4126.86 100.2324.89 102.8330.59 104.0734.65 112.4637.53 122.13];%%D=Distanse(X); %计算距离矩阵N=size(D,1); %城市的个数%% 初始解S1=randperm(N); %随机产生一个初始路线%% 画出随机解的路径图DrawPath(S1,X)pause(0.0001)%% 输出随机解的路径和总距离disp('初始种群中的一个随机值:')OutputPath(S1);Rlength=PathLength(D,S1);disp(['总距离：',num2str(Rlength)]);%% 计算迭代的次数TimeTime=ceil(double(solve(['1000*(0.9)^x=',num2str(Tend)]))); count=0; %迭代计数Obj=zeros(Time,1); %目标值矩阵初始化track=zeros(Time,N); %每代的最优路线矩阵初始化%% 迭代while T0>Tendcount=count+1; %更新迭代次数temp=zeros(L,N+1);for k=1:L%% 产生新解S2=NewAnswer(S1);%% Metropolis法则判断是否接受新解[S1,R]=Metropolis(S1,S2,D,T0); %Metropolis 抽样算法temp(k,:)=[S1 R]; %记录下一路线的及其路程end%% 记录每次迭代过程的最优路线[d0,index]=min(temp(:,end)); %找出当前温度下最优路线if count==1 || d0<Obj(count-1)Obj(count)=d0; %如果当前温度下最优路程小于上一路程则记录当前路程 elseObj(count)=Obj(count-1);%如果当前温度下最优路程大于上一路程则记录上一路程endtrack(count,:)=temp(index,1:end-1); %记录当前温度的最优路线T0=q*T0; %降温fprintf(1,'%d\n',count) %输出当前迭代次数end%% 优化过程迭代图figureplot(1:count,Obj)xlabel('迭代次数')ylabel('距离')title('优化过程')%% 最优解的路径图DrawPath(track(end,:),X)%% 输出最优解的路线和总距离disp('最优解:')S=track(end,:);p=OutputPath(S);disp(['总距离：',num2str(PathLength(D,S))]);disp('-------------------------------------------------------------')。

基于遗传算法的智能优化设计与应用研究随着科技的飞速发展，智能优化设计在各个领域中的应用越来越广泛。

其中，基于遗传算法的智能优化设计已成为研究的热点。

本文将对基于遗传算法的智能优化设计进行探讨，并分析其在实际应用中的优势。

一、遗传算法的原理及应用遗传算法是通过模拟自然界的进化过程，利用计算机实现优化搜索的方法。

其基本原理为：将问题抽象为一组基因，根据问题的特点设计适应度函数，通过采用遗传算子（交叉、变异、选择）对基因进行迭代，以得到较优的解。

遗传算法的应用非常广泛，如机器学习、数据挖掘、模式识别、控制系统优化、网络优化、电力系统优化等。

在实际应用中，遗传算法通过多参数优化来进行设计，可以最大限度地满足设计要求，提高了设计的效率和准确性。

二、基于遗传算法的智能优化设计方法以汽车设计为例，基于遗传算法的智能优化设计具体步骤如下：（1）确定目标函数根据设计要求确定优化目标函数。

如外观美观度、车身稳定性、燃油经济性、可行驶里程等。

（2）构建初始种群将设计问题抽象为基因表达，并通过初始随机化生成多个个体。

（3）计算适应度利用目标函数计算每个个体的适应度值，判断其是否符合设计要求。

（4）进行选择选择适应度值较高的个体，作为下一代种群的种子。

（5）进行交叉和变异通过交叉和变异操作，生成下一代种群，循环遗传直至最优解的产生。

（6）评估结果对产生的解进行评估，若达到目标要求，则结束迭代。

三、基于遗传算法的智能优化设计的优势与传统的优化设计方法相比，基于遗传算法的智能优化设计具有以下优势：（1）全局搜索能力较强基于遗传算法的智能优化设计可以实现全局搜索，从而寻找问题的全局最优解。

与暴力搜索算法相比，其搜索深度更高，可以跳过局部最优解，得到更优的结果。

（2）适用范围广由于遗传算法适用于各种类型的问题，因此其适用范围非常广。

无论是参数优化、约束优化、多模态优化，都可以采用遗传算法进行求解。

（3）高效稳定遗传算法采用并行计算的方式，能够有效提高计算速度。

人工智能遗传算法论文(2)人工智能遗传算法论文篇二人工智能之遗传算法论文摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。

但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。

本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。

该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。

选择了几个典型非线性方程组，考察它们的最适宜解。

关键词：非线性方程组;混合遗传算法;优化1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。

它将适者生存、结构化但同时又是随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。

每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。

随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。

在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。

因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。

传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。

很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。

而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。

而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。

专业选修课期末考核（论文）遗传算法及其应用浅析学院：专业：班级：学号：学生姓名：指导教师：2015年 6 月 1 日贵州大学贵州大学论文（设计）诚信责任书本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。

毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。

特此声明。

论文（设计）作者签名：日期：目录第一章绪论 (4)第二章遗传算法介绍 (5)2.1遗传算法介绍 (5)2.2遗传算法的产生和发展 (5)2.3 遗传算法的基本求解步骤 (6)2.3.1 编码： (6)2.3.2初始化： (6)2.3.3估计适应度： (6)2.3.4再生(选择): (6)2.3.5 交叉: (6)2.3.6 变异： (6)2.3.7 重复： (7)2.4 遗传算法流程图： (7)第三章遗传算法的应用概述 (8)3.1 TSP 问题描述 (8)3.2 遗传算法用于TSP 问题 (9)3.2.1 编码表示 (9)3.2.2 初始化群体和适应度函数及其终止条件的设定 (9)3.2.3 选择算子 (10)3.2.4 交叉算子 (10)3.2.5 变异算子 (11)3.2.6 TSP问题的总结 (11)第四章应用举例 (12)4．1 问题陈述 (12)4．2 详细解答过程 (12)4.2.1 问题分析 (12)4.2.2 实验原理与数学模型 (13)4.2.3 MATLAB求解结果 (15)4．3 求解结果验证与反思 (16)第五章附录 (17)5．1 Matlab程序代码 (17)参考文献 (22)【摘要】：遗传算法（Genetic Algorithm,GA）是近年来迅速发展起来的一种全新的随机搜索与优化算法，是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。

它的研究历史比较短，早期是一种试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。

基于遗传算法的中药药对挖掘系统的设计与实现摘要用数据挖掘技术研究了中药方剂配伍的规律。

主要工作：分析了关联规则存在的问题，引入双向关联规则的概念；介绍了遗传算法的基本原理，研究了遗传算法在数据挖掘中的应用；将方剂库转换为位图矩阵，大大提高搜索效率；开发了一个基于遗传算法的中药药对药组挖掘系统。

论文组织如下：介绍了研究背景和意义；阐述了相关的理论基础；提出了系统的设计方案；详细展示了基于遗传算法的双向关联规则挖掘系统的实现过程，包括位图矩阵的实现，个体的编码方法，适应度函数的设计，规则的提取，选择、交叉、变异等遗传操作的实现等；利用脾胃类方剂库对系统进行了测试，并对测试结果进行了分析。

结果证明：该系统能够快速高效地从方剂库中找出具有重要意义的药对药组，对中医药的研究发展有一定意义。

关键词：数据挖掘；置信度；双向关联规则；遗传算法The Design and Implementation of Chinese Medicine Groups Mining System based on Genetic AlgorithmAbstractThis paper researches the compatibility of chinese medicine prescriptions by data mining techniques. The main contributions include: analyzes the problems in the association rules, and introduces the concept of the bidirectional association rule; presents the foundation principle of genetic algorithm(GA), and studys the application of GA in the data mining; converts chinese medicine prescriptions database to a bitmap matrix, which greatly enhances the efficiency of search; develops a chinese medicine groups mining system based on GA. The paper is organized as follows: Section 1 introduces the background and significance; Section 2 sets forth the basis of the relevant theories; Section 3 proposes the design project of the system; Section 4 detailedly shows the implementation of the system, including the implementation of bitmap matrix, the individual coding method, the design of fitness function, rules of the extraction, genetic operations. Section 5 gives a test of the system on the prescriptions database about spleen and stomach, and analyzes the results. It is proved that this system can find important and significant Chinese Medicine Groups from the prescriptions database, and is meaningful for the research of Chinese medicine.Key words:Data mining; Confidence; Bidirectional association rule; Genetic algorithm目录论文总页数：24页1 引言 (1)1.1 背景 (1)1.2 意义 (1)2 理论基础 (1)2.1 关联规则及存在的问题 (1)2.2 双向关联规则 (2)2.3 遗传算法简介 (3)3 需求分析及设计方案 (4)4 基于遗传算法的双向关联规则挖掘算法具体流程及实现 (6)4.1 位图矩阵实现 (6)4.2 编码 (9)4.3 适应度函数 (11)4.3.1 适应度函数设计 (11)4.3.2 适应度函数的实现 (11)4.4 规则的提取 (14)4.5 遗传操作 (15)4.6 算法流程 (18)5 测试 (18)结论 (21)参考文献 (21)致谢 (23)声明 (24)1引言1.1背景我国作为最大的中药材资源国，有着传统中医药文明的发祥地的地位，但是如今正面临着诸多挑战。

遗传算法的研究与优化遗传算法是一种模仿自然选择和遗传机制的优化算法，它可以用来寻找复杂问题的最优解。

在过去的几十年里，遗传算法一直被广泛应用于各种领域，如优化问题、机器学习、数据分析等。

本文将对遗传算法的研究与优化进行深入探讨，以期为读者提供全面且深入的了解。

遗传算法最早由美国学者John Holland在20世纪60年代提出，它是一种模拟自然选择和遗传机制的优化方法。

遗传算法借鉴了生物学中的进化理论，通过模拟自然界中的遗传、变异、选择等机制来不断寻找最优解。

遗传算法具有良好的自适应性和全局搜索能力，因此被广泛应用于各种领域。

遗传算法的基本原理是通过一系列的操作（交叉、变异、选择）来不断地优化种群中的个体，直至找到最优解为止。

随机生成一组初始解作为种群，然后通过交叉操作来产生新的个体，再通过变异操作来引入一定程度的随机性，最后根据适应度函数的评价来选择优秀的个体。

通过不断的迭代操作，逐步逼近最优解。

在遗传算法的研究中，有很多值得关注的问题。

首先是遗传算法的收敛性能问题，即如何加快算法的收敛速度，降低收敛误差。

其次是算法的稳定性和鲁棒性问题，即在不同的问题领域中，如何提高算法的稳定性和鲁棒性。

还有算法的并行化和分布式处理问题，即如何利用并行计算和分布式处理技术来提高算法的计算效率。

为了解决这些问题，许多学者进行了大量的研究工作。

他们提出了许多改进的遗传算法，如基于多种群的遗传算法、基于自适应权重的遗传算法、基于混合策略的遗传算法等。

这些改进使遗传算法在不同领域中取得了很好的效果，如在工程优化、数据挖掘、智能控制等方面都得到了广泛应用。

遗传算法还可以与其他优化算法相结合，形成混合优化算法。

比如将遗传算法与模拟退火算法、粒子群算法等相结合，可以充分利用各种优化算法的优点，进一步提高算法的优化能力。

对于遗传算法的优化问题，研究者们也提出了许多有效的方法。

以改进遗传算法的交叉和变异算子为例，通过优化交叉和变异算子的参数和策略，可以显著提高算法的搜索能力和收敛速度。

第27卷 第6期2010年12月黑龙江大学自然科学学报J OURNAL OF NATURAL SC IE N CE O F HEILONG JI ANG UN I V ERS I TY V o l 27N o 6D ece m ber ,2010基于神经网络模式的遗传算法在CR M 的数据挖掘优化研究冯 锋1,2, 徐 琪1(1.东华大学旭日管理学院,上海200051;2.宁夏大学数学计算机学院,银川750021)摘 要:提出了一种有利于优化CRM 的基于神经网络模式的遗传算法,在对该算法仿真研究的基础上,将其应用于CRM 的数据挖掘中,用于优化BP 神经网络模型的拓扑结构和连接权值,并给出了相关的遗传操作和实验结果。

通过论证分析认为,该算法克服了原有几种用遗传算法优化CRM 神经网络数据挖掘模型的缺点和不足,提高了数据的精度和准确性,具有广泛的应用价值。

关键词:C RM;BP 神经网络;数据挖掘模型;遗传算法中图分类号:TP183文献标志码:A 文章编号:1001-7011(2010)06-0796-04收稿日期:2010-07-12基金项目:国家自然科学基金资助项目(70772073);宁夏自然科学基金资助项目(NZ0824)作者简介:冯 锋(1971-),男,副教授,博士研究生,主要研究方向:供应链及大系统集成,E m a i :l feng -@f .cn通讯作者:徐 琪(1963-),女,教授,博士生导师,主要研究方向:电子商务系统与理论,供应链及大系统集0 引 言数据挖掘(Date M i n i n g)的任务就是提取隐含于数据库中的、未知的、有用的、不一般的信息或知识,数据挖掘又称为数据库的知识发现。

客户关系管理(Custo m er R elationsh i p M anage m en,t CRM )作为一种新的管理模式、业务营销理念和信息技术前沿产品,是信息技术与业务管理相结合的产物。

学校代码 10126 学号 00708037 分类号密级本科毕业论文基于遗传算法的图像阈值分割学院、系数学科学学院计算数学系专业名称信息与计算科学年级 2007级学生姓名刘家祥指导教师曹军2011年 5月 20 日内容摘要图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。

图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。

如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。

遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。

遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。

本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。

关键词：图像分割，遗传算法，阈值分割AbstractImage segmentation refers to the image into regions each with characteristics and goals of the technology to extract and process of interest. Segmentation is a segmentation based on gray value, gray value of each pixel through the predetermined threshold value and comparing the image segmentation. How to determine the most appropriate threshold is the key to handling image segmentation, which has naturally become the focus of segmentation algorithms.Genetic algorithm is a biological theory of evolution and genetic mechanism of natural selection in biological evolution simulation method to calculate the optimal solution. Genetic algorithm has many advantages, such as robustness, parallel, adaptive, and fast convergence, can be used in the field of image processing image segmentation technique to determine the split threshold.In this paper, genetic algorithm based on minimum error threshold, the largest class variance (Otsu method) and the best histogram entropy (KSW entropy method) are three ways to split the image.Keywords : Image segmentation, genetic algorithms, threshold目录第一章绪论 .................................................. - 1 - 第二章遗传算法概述 ........................................ . - 2 -2.1遗传算法的研究历史....................................... - 2 -2.2生物背景................................................. - 2 -2.3遗传算法的基本思想....................................... - 3 -2.4遗传算法的几个概念....................................... - 4 -2.4.1适应度函数......................................... - 4 -2.4.2遗传算法最常用的算子............................... - 4 -2.5遗传算法运算的基本流程................................... - 5 - 第三章图像分割的现状 ........................................ - 7 -3.1图像分割简介............................................. - 7 -3.2图像分割方法............................................. - 8 -3.2.1基于边缘检测的分割................................. - 8 -3.2.2基于区域的分割..................................... - 8 -3.2.3边缘与区域相结合的分割............................. - 9 -3.3阈值选取................................................. - 9 - 第四章基于遗传算法的图像阈值分割 ........................... - 10 -4.1图像阈值................................................ - 10 -4.2阈值分割的原理.......................................... - 10 -4.3最小误差阈值法.......................................... - 11 -4.3.1最小误差法图像阈值分割............................ - 11 -4.3.2 利用遗传算法来改进最小误差法...................... - 12 -4.4 最大类间方差法（Otsu法）............................... - 13 -4.4.1最大类间方差法（Otsu法）阈值分割.................. - 13 -4.4.2 Otsu阈值分割的遗传算法设计........................ - 15 -4.5 KSW熵法................................................ - 17 -4.5.1 KSW熵阈值分割................................... - 17 -4.5.2 KSW单阈值分割的遗传算法设计..................... - 18 -4.5.3 KSW双阈值分割的遗传算法设计..................... - 19 - 第五章基于新的遗传算法的图像分割 ........................... - 25 -5.1混沌遗传算法............................................ - 25 -5.2量子遗传算法............................................ - 25 -5.3免疫遗传算法............................................ - 25 - 结论 .......................................................... - 26 - 致谢 .......................................................... - 27 - 参考文献: ..................................................... - 28 -内蒙古大学本科学年论文第- 1 - 页基于遗传算法的图像阈值分割第一章绪论图像分割是图像处理与计算机视觉的基本问题之一，是图像处理到图像分析的关键步骤。

遗传算法在函数优化中的应用目录1.绪论 (2)概述 (2)遗传算法的发展历史与研究进展 (4)2.遗传算法流程与应用举例 (6)遗传算法中各重要因素分析 (6)2.2重要参数设置 (8)简单的遗传算法运算示例 (8)3.遗传算法在函数优化应用中的性能研究 (12)遗传算法在实际应用中的性能影响因素 (12)函数优化问题的描述 (14)求解函数优化问题的最优交叉、变异率组合的研究 (16)一种求解函数优化问题的自适应遗传算法 (19)小结 (21)结束语 (21)参考文献 (22)致谢 (23)1.绪论遗传算法(genetic algorithms简称GA)由美国密歇根大学的John H．Holland教授等创立的一类仿生型的优化算法。

它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础、模拟生物进化过程、自适应启发式全局优化的搜索算法。

由于遗传算法无需过多地考虑问题的动力学信息，如连续、可微等，该算法结构简单，并且具有全局搜索能力、信息处理的隐并行性、鲁棒性和可规模化等优点，它在思路上突破原有的最优化方法的框架，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，现己被广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，并且在经济和决策方面也有很好的应用，是21世纪有关智能计算中的关键技术之一。

遗传算法的处理对象不是参数本身，而是对参数进行了编码的个体，因此不仅可以对传统的目标函数优化求解，而且可以处理诸如矩阵、树和图等结构形式的对象，用适应度函数同时对搜索空间的多个解进行评估，它将每个可能的问题表示为“染色体”，然后按遗传学规律进行选择、交叉和变异操作，直到满足终止条件为止。

隐含并行性和全局搜索性是遗传算法的两大特点，前者可使遗传算法只需检测少量的结构就能反映搜索空间的大量区域，后者则使遗传算法具有良好的稳健性。

在遗传算法的诸多应用中，函数优化是最显而易见的应用，也是经典的应用。

遗传算法的应用及研究动向5则范文第一篇：遗传算法的应用及研究动向遗传算法的应用及研究动向摘要本文主要介绍了遗传算法的基本概念和基本原理，分析说明了遗传算法应用领域，指出了遗传算法在应用中的几个关键问题，同时简要介绍了遗传算法研究新动向及存在的问题。

关键词遗传算法；编码机制；遗传算子；适应度函数一、遗传算法的基本原理遗传算法类似于自然进化，通过作用于染色体上基因寻找最好的染色体来求解问题。

与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对遗传算法所产生的染色体有更多的繁殖机会。

在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合成下一代新的种群，对这个新种群进行下一轮进化[1]。

二、遗传算法的应用遗传算法在应用中最关键的问题有如下3 个[2-3]。

（1）串的编码方式。

本质是问题编码。

一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。

串长度及编码形式对算法收敛影响极大。

（2）适应函数的确定。

适应函数（fitness function）也称对象函数（object function），这是问题求解品质的测量函数；往往也称为问题的“环境”。

一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

（3）遗传算法自身参数设定。

遗传算法自身参数有3 个，即群体大小n、交叉概率Pc 和变异概率Pm。

群体大小n 太小时难以求出最优解，太大则增长收敛时间。

一般n＝30-160。

交叉概率Pc 太小时难以向前搜索，太大则容易破坏高适应值的结构。

一般取Pc=0.25-0.75。

变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。

一般取Pm＝0．01-0．2。

遗传算法的主要应用领域[4-5]在于函数优化（非线性、多模型、多目标等），机器人学（移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化等），控制（瓦斯管道控制、防避导弹控制、机器人控制等），规划（生产规划、并行机任务分配等），设计（VLSI 布局、通信网络设计、喷气发动机设计等），组合优化（TSP 问题、背包问题、图分划问题等），图像处理（模式识别、特征提取、图像恢复等），信号处理（滤波器设计等），人工生命（生命的遗传进化等）。

基于遗传算法的优化问题求解算法研究随着科技的不断发展和应用领域的拓展，人们对于求解优化问题的需求也越来越多。

在许多实际问题中，优化问题往往是一个复杂且多变的挑战，而遗传算法作为一种常用的优化算法在解决这类问题上具有一定的优势。

本文将从遗传算法的原理、编码和适应度函数设计以及收敛性分析等方面，对基于遗传算法的优化问题求解算法进行研究探讨。

首先，遗传算法是一种模拟自然界生物进化过程的优化算法。

其基本思想是通过模拟遗传、变异、选择和交叉等遗传过程，以实现求解优化问题的目标。

遗传算法的主要步骤包括个体的初始化、适应度评估、选择、交叉、变异和新一代个体的生成等。

在遗传算法中，编码是将问题的解表示为一条染色体的过程。

合适的编码方式能够更好地表征问题的特性，并提高算法的求解效率。

常用的编码方式包括二进制编码、实数编码和排列编码等。

其中，二进制编码是最常用的一种编码方式，可以将问题的解空间划分为多个离散的区域，方便进行遗传操作。

而实数编码则可以更灵活地表示连续型变量，适用于某些需要高精度的问题。

在选择操作中，通过适应度函数对个体的质量进行评估，以决定哪些个体能够生存下来并参与繁殖。

适应度函数的设计很大程度上决定了遗传算法的性能。

合适的适应度函数应当能够充分反映个体的优劣程度，并且具有较好的连续性和可导性等特性。

根据问题的具体特点，适应度函数可以采用不同的形式，如单目标适应度函数、多目标适应度函数和约束函数等。

交叉和变异是遗传算法中最重要的两个遗传操作。

交叉操作通过模拟生物个体的基因重组过程，将两个个体的染色体段互换，从而获得新的个体。

变异操作则引入一定的随机性，通过改变个体的染色体中的一部分基因内容来增加种群的多样性。

交叉和变异过程的设计既要保留良好的个体特征，又要保证种群的多样性。

合适的交叉和变异操作能够提高算法的全局搜索能力，并有助于避免陷入局部最优解。

收敛性分析是评价遗传算法性能的重要指标之一。

在算法求解过程中，收敛性分析可以帮助我们了解算法是否能够在合理的时间内找到近似最优解，并对算法的计算复杂度进行评估。

用遗传算法对FRP材料进行抗弯和抗剪强度的设计摘要：对用于混凝土结构加固的FRP材料进行不连续的最优化设计，可采用遗传算法这种设计程序。

其主要目的是让增强加固结构中梁的抗弯和抗剪强度的费用达到最小值。

根据欧洲混凝土加固规范与欧洲第二套设计规范相结合，来定义承载能力极限状态和正常使用极限状态。

遗传算法是通过一条最优化路线来选择设计方案。

因此要进行不同的试验来对比，找出遗传算法中不同的参数和特征所发挥的作用。

并且，在设计程序的时候要考虑欧洲设计规范中的个性。

关键词：纤维增强复合材料，最优法，计算，准则，加固混凝土Flexural and Shear Design of FRP Plated RC StructuresUsing a Genetic AlgorithmAbstract:A design procedure implementing a genetic algorithm has been developed for the discrete optimization of the design of fiber-reinforced polymer FRP RC structures. The aims of the procedure are to minimize the material costs of strengthening RC beams for flexural and shear behavior. The ultimate limit states and the serviceability limit states are defined according to the European design guidelines for the use of FRP reinforcement in RC structures in accordance with the design format of Eurocode No. 2. The design variables are encoded in order to make use of genetic algorithms as an optimization routine. Comparative studies are presented to study the effect of the different parameters and characteristics of the genetic algorithm. Different aspects covered in the European design code are also considered in the design procedure.key words:Fiber reinforced polymers; Optimization; Computation; Guideline; Reinforced concrete.引言近年来工业迅猛发展，加固行业变得越来越重要了。

毕业设计（论文）基于遗传算法求解背包问题院别专业名称班级学号学生姓名指导教师2012年6月15日基于遗传算法求解背包问题摘要背包问题(Knapsack problem)是一种组合优化的NP完全问题,本文首先介绍了基本遗传算法的基本原理、特点及其基本实现技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况。

并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及合适的遗传算子。

最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。

关键词：背包问题，遗传算法，遗传算子Genetic Algorithm for KPAuthor：Yang DongTutor：Kong ZhiAbstractKP (Knapsack Problem) is a combinatorial optimization of NP - complete problem. The primary knowledge, characteristics and the basic techniques of GA are introduced firstly. The encoding model and genetic operators (including selection operation, crossover operation and mutation operation) solving KP are discussed secondly. Combined with examples of knapsack problem, we have given the specific encoding method, operating parameters, popsize, maxgeneration, and suitable genetic operator. At last, the application of genetic algorithm is simple presented, and the prospect for the future of genetic algorithm in solving KP has been given.Key Words: KP, genetic algorithm, genetic operators目录1绪论 (III)1.1 引言 (1)1.2 背包问题概述 (1)1.2.1 背包问题的描述 (2)1.2.2 研究背包问题的意义 (9)1.3 遗传算法 (10)1.3.1 遗传算法概述 (10)1.3.2 遗传算法的特点 (10)1.3.3 遗传算法的应用领域 (11)2遗传算法的基本原理 (13)2.1 基本流程 (14)2.2 编码 (14)2.3 适应度函数 (15)2.4 遗传算子 (15)2.4.1 选择算子 (15)2.4.2 交叉算子 (17)2.4.3 变异算子 (17)2.5 参数控制 (18)2.5.1 群体规模 (18)2.5.2 交叉概率 (18)2.5.3 变异概率 (18)2.6 算法结束条件控制 (19)3求解实现背包问题的遗传算法 (20)3.1 0_1背包问题中染色体的表示 (20)3.2 算法求解01背包问题时用到的参数 (20)3.3 选择操作 (20)3.4 交叉操作 (21)3.5 精英策略 (22)3.6 变异操作 (22)3.7 代际更新 (23)3.8 算法的终止 (23)3.9 仿真结果与测试 (24)3.9.1 不同交叉概率下所的测试结果 (25)3.9.2 极端数据对结果的影响 (27)3.9.3 仿真结果总结 (29)结论 (31)致谢 (32)参考文献 (33)附录 (34)1绪论1.1引言现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。