遗传算法及其改进措施
- 格式：docx
- 大小：3.96 MB
- 文档页数：15
下载文档原格式
合集下载
用于求解TSP问题的遗传算法改进
用于求解TSP问题的遗传算法改进一、TSP问题简介TSP问题，全称Traveling Salesman Problem，即旅行商问题。
所谓TSP问题是指，给定一些点和每一对点之间的距离，求出一条遍历每个点恰好一次的最短路径，该问题的解决方法对实际问题中的路径规划和优化有着很大的参考价值。
二、遗传算法的基本思想遗传算法，是模拟自然界中生物遗传进化过程的一种演化计算方法。
它通过模拟生物的繁殖、变异、适应性等生命过程来寻找问题的最优解。
其基本的过程如下：1. 初始化：随机生成一个初始群体，每个个体表示一种可能的解决方案。
2. 选择：根据适应度函数，选择一定数量的优秀个体作为繁殖的父亲。
3. 交叉：将所选父亲进行交叉操作，生成新的子代个体。
4. 变异：对于一部分子代个体，进行变异操作。
5. 替换：用新的子代个体替换掉一部分原有的个体，形成新一代群体。
6. 结束条件：当某种条件达到时结束算法，否则返回步骤二。
在TSP问题中，遗传算法的基本实现方法如下：1.初始化：随机生成一个初始群体，每个个体表示一个解决方案，其中每个基因表示一个城市的编号。
例如，假设有10个城市，则每个个体就是由这10个城市编号随机排列组成的，例如：1-2-5-8-4-3-7-9-6-10等。
2.适应度函数：对于每个个体，计算其总路程，将总路程作为适应度函数的值。
4.交叉：将所选父亲进行交叉操作，生成新的子代个体，交叉方式一般有：顺序交叉法、部分映射交叉法、环形交叉法、边交叉法等。
5.变异：对于一部分子代个体，进行变异操作，变异的方式一般是：交换变异、倒位变异、随机抽样变异等。
7.结束条件：当达到一定条件时结束算法，比如迭代次数达到上限或者群体的适应度达到一定的水平。
传统的遗传算法在求解TSP问题时，存在一些问题：1.收敛速度慢：由于集合了交叉、变异等算子，每一代都要进行大量的计算，所以收敛速度慢。
2.易受陷入局部最优解：由于遗传算法采用的是局部搜索策略，所以可能会陷入到局部最优解中。
遗传算法在数据库优化中的解决方案
遗传算法在数据库优化中的解决方案数据库优化是提高数据库性能和效率的关键步骤，而遗传算法作为一种优化算法，可以在数据库优化中发挥重要作用。
本文将探讨遗传算法在数据库优化中的解决方案。
一、遗传算法简介遗传算法是一种模拟自然选择和遗传机制的优化算法。
它通过模拟生物进化过程中的选择、交叉和变异等操作，来搜索问题的最优解。
遗传算法具有全局搜索能力和自适应性，适用于复杂问题的优化。
二、数据库优化问题在数据库中，性能问题常常涉及查询优化、索引设计、表结构调整等方面。
传统的优化方法往往需要人工经验和反复试错，效率低下且不一定能找到最优解。
而遗传算法可以通过不断迭代的方式，自动搜索最优解，提高数据库性能。
三、遗传算法在数据库查询优化中的应用数据库查询优化是提高查询效率的关键。
遗传算法可以通过优化查询语句的执行计划，从而提高查询性能。
具体而言，遗传算法可以通过选择合适的索引、调整表连接顺序、优化查询语句等方式，提高查询效率。
四、遗传算法在索引设计中的应用索引是提高数据库查询效率的重要手段。
传统的索引设计往往需要根据经验和统计数据进行调整，效果不一定理想。
而遗传算法可以通过自动搜索最优索引的方式，提高查询性能。
它可以通过选择合适的索引字段、调整索引顺序等方式，找到最优索引组合。
五、遗传算法在表结构调整中的应用数据库表结构的设计对性能有重要影响。
传统的表结构调整方法需要手动调整，效率低下。
而遗传算法可以通过自动搜索最优表结构的方式，提高数据库性能。
它可以通过调整表字段顺序、拆分大表等方式，优化表结构，提高查询效率。
六、遗传算法的优势和局限性遗传算法在数据库优化中具有以下优势：首先，它可以自动搜索最优解，减少了人工经验的依赖；其次，它具有全局搜索能力，可以找到全局最优解；此外，它具有自适应性，能够适应不同的问题。
然而，遗传算法也存在一些局限性，例如计算复杂度较高、算法参数的选择等问题。
七、结论遗传算法作为一种优化算法，在数据库优化中具有重要的应用价值。
遗传算法在组合优化中的解决方案
遗传算法在组合优化中的解决方案组合优化是一种重要的问题求解方法，它在现实生活中的应用非常广泛。
而遗传算法作为一种启发式搜索算法，被广泛应用于组合优化问题的求解中。
本文将探讨遗传算法在组合优化中的解决方案，并分析其优势和应用场景。
一、遗传算法的基本原理遗传算法是一种模拟自然进化过程的优化算法。
其基本原理是通过模拟遗传、变异和选择等过程，逐步优化问题的解。
具体而言，遗传算法主要包括以下几个步骤：1. 初始化种群：随机生成一定数量的个体，每个个体代表问题的一个可能解。
2. 评估适应度：根据问题的特定评价函数，计算每个个体的适应度值，用于衡量其解的优劣程度。
3. 选择操作：根据适应度值，选择一部分个体作为父代，用于产生下一代个体。
4. 交叉操作：通过交叉操作，将父代个体的某些特征进行组合，生成新的个体。
5. 变异操作：对新生成的个体进行变异操作，引入一定的随机性，增加问题的搜索空间。
6. 重复步骤2至5，直到满足终止条件。
二、遗传算法在组合优化中的应用遗传算法在组合优化中有广泛的应用，例如旅行商问题、背包问题、调度问题等。
下面以旅行商问题为例，说明遗传算法的应用。
旅行商问题是一个经典的组合优化问题，其目标是找到一条最短的路径，使得旅行商能够依次访问多个城市并最终回到起点。
遗传算法可以通过以下步骤解决该问题：1. 初始化种群：随机生成一定数量的路径，每个路径代表旅行商的一种可能行走顺序。
2. 评估适应度：根据路径的总长度，计算每个路径的适应度值。
3. 选择操作：根据适应度值，选择一部分路径作为父代。
4. 交叉操作：通过交叉操作，将父代路径的某些城市进行组合，生成新的路径。
5. 变异操作：对新生成的路径进行变异操作，引入一定的随机性。
6. 重复步骤2至5，直到满足终止条件。
通过以上步骤，遗传算法可以不断优化路径，最终找到一条最短的路径解决旅行商问题。
三、遗传算法的优势和应用场景遗传算法在组合优化中具有以下优势：1. 并行搜索能力：遗传算法可以同时搜索多个解，提高问题的求解效率。
最佳遗传算法参数调优方法
最佳遗传算法参数调优方法遗传算法是一种模拟自然界中生物进化过程的优化算法。
在解决复杂问题和优化函数方面具有广泛的应用。
然而，遗传算法的性能很大程度上取决于参数的选择。
本文将介绍一些最佳的遗传算法参数调优方法，以帮助提高算法的性能。
1. 交叉率的选择交叉是遗传算法中的一个重要操作，用于产生新的个体。
交叉率决定了父代个体中被交叉的比例。
如果交叉率过高，可能导致早熟收敛和搜索空间的过早收缩。
相反，如果交叉率过低，可能导致搜索的速度过慢。
因此，选择一个合适的交叉率至关重要。
一种常见的方法是采用自适应交叉率。
在算法开始时，可以使用较高的交叉率，以便更好地探索搜索空间。
随着算法的进行，可以逐渐降低交叉率，以便更多地利用已经找到的优秀解。
这样可以平衡探索和利用的关系，提高算法的性能。
2. 变异率的选择变异是遗传算法中的另一个重要操作，用于引入新的基因信息。
变异率决定了个体中基因发生变异的概率。
如果变异率过高，可能导致搜索过于随机，难以收敛到最优解。
相反，如果变异率过低，可能导致搜索的局部最优解。
一种常见的方法是采用自适应变异率。
在算法开始时，可以使用较高的变异率，以便更好地探索搜索空间。
随着算法的进行，可以逐渐降低变异率，以便更多地利用已经找到的优秀解。
这样可以平衡探索和利用的关系，提高算法的性能。
3. 种群大小的选择种群大小是指每一代中个体的数量。
种群大小的选择对算法的性能有很大影响。
如果种群大小过小，可能导致搜索的多样性不足，难以找到全局最优解。
相反，如果种群大小过大，可能导致计算资源的浪费。
一种常见的方法是采用自适应种群大小。
在算法开始时，可以使用较大的种群大小，以便更好地探索搜索空间。
随着算法的进行，可以逐渐减小种群大小，以便更多地利用已经找到的优秀解。
这样可以平衡探索和利用的关系，提高算法的性能。
4. 选择算子的选择选择算子用于选择较优个体作为下一代的父代。
选择算子的选择对算法的性能有很大影响。
常见的选择算子有轮盘赌选择、锦标赛选择等。
遗传算法基本原理及改进
遗传算法基本原理及改进编码方法：1、二进制编码方法2、格雷码编码方法3、浮点数编码方法。
个体长度等于决策变量长度4、多参数级联编码。
一般常见的优化问题中往往含有多个决策变量，对这种还有多个变量的个体进行编码的方法就成为多参数编码方法。
多参数编码的一种最常用和最基本的方法是：将各个参数分别以某种方式进行编码，然后再将它们的编码按照一定顺序连接在一起就组成了标识全部参数的个体编码。
5、多参数交叉编码：思想是将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏掉。
在进行多参数交叉编码时，可先对各个参数进行编码；然后去各个参数编码串的最高位连接在一起，以他们作为个体编码串前N位编码，同上依次排列之。
改进遗传算法的方法：（1）改进遗传算法的组成成分或实用技术，如选用优化控制参数、适合问题的编码技术等。
（2）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。
（3）采用混合遗传算法（4）采用并行算法（5）采用非标准的遗传操作算子改进的遗传算法：（1）分层遗传算法（2）CHC算法（3）messy遗传算法；（4）自实用遗传算法（Adaptive Genetic Algorithm）（5）基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA）。
（6）并行遗传算法（Parallel Genetic Algorithm）（7）混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火算法相结合的混合遗传算法。
解决标准遗传算法早熟收敛和后期搜索迟钝的方案（1）变异和交叉算子的改进和协调采用将进化过程划分为渐进和突变两个不同阶段采用动态变异运用正交设计或均匀设计方法设计新的交叉和变异算子（2）采用局部搜索算法解决局部搜索能力差的问题（3）采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题（4）收敛速度慢的解决方法；产生好的初始群体利用小生境技术使用移民技术采用自适应算子采用与局部搜索算法相结合的混合遗传算法对算法的参数编码采用动态模糊控制进行未成熟收敛判断。
论文遗传算法的研究和改进
遗传算法的研究和改进遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题，本论文研究内容包括：小生境遗传算法的改进、自适应遗传算子的设计、免疫的进化算法。
本文主要工作如下：（1）遗传算法的起源、其基本概念以及研究概况;（2）遗传算法的基本理论.主要介绍了模式定理、积木块假说、内在并行性、Walsh模式变换、欺骗问题等;（3）基本遗传算法.主要介绍了编码、适应度函数、遗传操作等.（4）遗传算法的改进.主要介绍了分层遗传算法、CHC算法、messy遗传算法、自适应遗传算法、基于小生境技术的遗传算法、混合遗传算法等几种遗传算法的改进.（5）遗传算法的应用.关键词：遗传算法;进化计算;进化规划;进化策略;遗传操作;适应度函数;Walsh函数ABSTRACTGenetic algorithm is a kind of random searching method using lives’ natural selection and genetic mechanism. Its application predominance lies in complicated and non-linear problems, which are difficult for traditional searching methods. Three improved algorithms are proposed in the dissertation: improved niche genetic algorithm, improved adaptive genetic algorithm, genetic algorithm based on immune mechanism. They are summarized as following:Firstly, the dissertation analyses characters of several traditional genetic algorithms for niche. Following this, a new method, combined parallelism evolution technique for niches based on local competition with parent mutation mechanism, is proposed which improved the genetic algorithms for niche. Compared with genetic algorithm with sharing, it has some improvements in both converging velocity and precision.Secondly, analyzing the inadequacies of the evaluation indices for premature convergence, a novel improved adaptive genetic algorithm (IAGA) is described. The calculation result of an example shows that IAGA is able to get the real-time information of population diversity during the process of evolution.Finally, applying the immune mechanism to genetic algorithm, the immune genetic algorithm expatiated on this paper comes over the phenomenon of premature in some extent. The result of experiment shows that the global convergence and searching velocity are both improved.Keyword: genetic algorithms, evolution strategy, Walsh function第一章 绪论§1.1 引言遗传算法（Genetic Algorithm ——GA ），是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法[1]。
遗传算法及其改进措施
优化算法大作业一、题目本文利用遗传算法，依次完成下面三个目标函数的寻优：1Generalized Rosen brock’s valley Function048.2048.2)1()(100)(max 112221<<--+-⋅=∑-=+i n i i i i x x x x x f2 Generalized Rastrigin's Function12.512.5)10)2cos(10()(min 112<<-+⋅-=∑-=i n i i i x x x x f π3 Schaffer’s Function44))(001.01(5.0)(sin 5.0),(min 222212222121<<-+*+-+-=i x x x x x x x f二、本文思路遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法，本文利用遗传算法分别对上述三种函数进行全局寻优，具体思路如下：1. 编码与解码1) 编码：假设某一参数的取值范围是[u min , u max ]，我们用长度为l 的二进制编码符号串来表示该参数，则它总共能够产生 2l 种不同的编码，编码的长度越长，对应的精度越高。
● 第一题变量的取值范围是[-2.048,2.048]，本文采取十位数的编码，那么精度为：3min max 110004.412-⨯=--=lu u δ ● 第二题变量的取值范围是[-5.12,5.12]，本文采取的是十二位数的编码，那么精度为：3min max 210501.212-⨯=--=l u u δ● 第三题变量的取值范围是[-4,4]，本文采取的是十三位数的编码，那么精度为：3minmax 310442.212-⨯=--=lu u δ2) 解码：假设某一个个体的编码是1221b b b b b L i i i --=，那么对应的解码公式为：δ⋅⋅+=-=∑)2(11min i li i b u x2. 个体适应度评价1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设 定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F (x )={f (x )−C min f (x )>C min0 f (x )≤C min其中min C 是函数最小值估计。
遗传算法调试及改进策略
遗传算法调试及改进策略遗传算法是一种基于生物进化理论的搜索算法，能够在解决各种优化问题上取得不错的效果。
但是在实际应用中，遗传算法的调试和改进策略也十分重要，本文就此展开讨论。
一、遗传算法的调试策略1、选择算子的调试选择算子是遗传算法中最重要的一步，其作用是筛选出适应度高的个体并进行后代产生。
调试选择算子时，需要注意以下几点：（1）选择算子应具有“竞争性”，即适应度高的个体应该有更大概率被选中，同时不适应度高的个体也有一定的被选中概率，以保证算法具有全局搜索能力。
（2）选择算子应具有一定的随机性，避免算法陷入局部最优解。
（3）选择算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
2、交叉算子的调试交叉算子是遗传算法中产生后代的重要步骤，其作用是将两个个体的染色体进行交叉，从而产生新的后代个体。
调试交叉算子时，需要注意以下几点：（1）交叉算子应该具有“多样性”，即不同类型的交叉方式应该有一定的概率被选中，以保证算法的全局搜索能力。
（2）交叉算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
（3）交叉算子的位置和长度应该有一定的随机性，以保证算法不会陷入局部最优解。
3、变异算子的调试变异算子是遗传算法中保持种群多样性的重要步骤，其作用是对个体的染色体进行随机变异，从而产生新的后代个体。
调试变异算子时，需要注意以下几点：（1）变异算子应该具有一定的“可控性”，即变异概率应该适当，过高或过低都会影响算法的性能。
（2）变异算子应该能够处理不同类型的编码方式，如二进制编码、实数编码等。
（3）变异算子的位置和长度应该有一定的随机性，以保证算法不会陷入局部最优解。
二、遗传算法的改进策略1、自适应参数调整在遗传算法中，参数的选择对算法的性能至关重要，如种群大小、交叉概率、变异概率等。
为了更好地平衡全局搜索和局部搜索之间的关系，可以采用自适应参数调整策略，根据算法的实际运行情况，动态地调整参数值。
改进遗传算法
5.停止准则
在基本的遗传算法中，一般采用最大迭代次数作为算法的 停止准则，此方法不太准确，因为可能在在最大的迭代次数 之前算法已经收敛，也可能在最大迭代次数时还没收敛，因 此采用另外一种停止准则，即根据种群的收敛程度，种群适 应值得一致性来判断是否算法停止。在算法的执行过程中保 留历史上最好的个体，观察指标
F Fmax
其中，F 为种群中所以个体适应值得平均值，Fmax 为所以个
体适应值得最大值，当上述指标趋近于1时，说明种群收 敛，此时算法停止。
谢谢
的是：循环交叉是用来解决指派这一类的问题的
2.变异修复策略
简单的二进制变异时候只需要把０变成１，１变成０， 而顺序编码的变异策略不能这样进行，一般由下面两种策略： ➢ 换位变异
➢ 换位变异是随机在染色体上选则两个基因，交换它们 的基因值
➢ 移位变异 ➢ 移位变异是任意选则一个基因，将其移到最前面。
的后期，希望选择压力较大，所以 k 取值较小，使不同个
体间的选择概率相差变大，种群将很快达到收敛，从而解决 了在最优解附近收敛较慢的问题。
➢ 幂律标定
幂律标定是采用如下的构造方式
F fα
其中，α是用来调节选择压力的，α >1时，选择压力加大， α<1时，选择压力减小，此标定比较费时，要针对不同问 题使用。
2.不合法编码的修复
对于普通的二进制编码，通常的交叉和变异不会改变 编码的合法性，但是对于顺序编码、实数编码，会造成编码 的不合法或者超出可行域，因此必须对不合法的编码进行处 理，通常的处理手段为拒绝或者修复。下面介绍修复的方法。
➢ 顺序编码的合法性修复 ➢ 实数编码的合法性修复
1. 顺序编码的修复
f1=1010,f2=1008,f3=1002,f4=1005,f5=1015
《改进遗传算法及其在TSP问题中的应用》范文
《改进遗传算法及其在TSP问题中的应用》篇一一、引言遗传算法是一种基于自然进化理论的搜索启发式算法，广泛应用于组合优化问题。
旅行商问题（Traveling Salesman Problem，简称TSP）作为典型的组合优化问题之一，吸引了众多研究者的关注。
本文旨在探讨改进遗传算法及其在TSP问题中的应用，通过分析现有遗传算法的优缺点，提出一种改进的遗传算法，并在TSP问题中验证其有效性和优越性。
二、遗传算法概述遗传算法模拟自然进化过程，通过种群个体的选择、交叉和变异等操作，实现全局搜索和优化。
其基本步骤包括初始化种群、计算个体适应度、选择操作、交叉操作和变异操作等。
三、现有遗传算法在TSP问题中的局限性在TSP问题中，遗传算法面临着多个挑战。
一方面，搜索空间随城市数量急剧增长；另一方面，由于问题的复杂性，传统遗传算法容易陷入局部最优解。
此外，传统遗传算法在处理城市间的距离计算和路径优化时，往往无法有效平衡全局搜索和局部搜索。
四、改进的遗传算法设计针对上述问题，本文提出一种改进的遗传算法。
该算法主要从以下几个方面进行优化：1. 初始化种群策略：采用更精细的编码方式，使个体更好地表示路径。
同时，引入随机性因素，扩大搜索空间。
2. 适应度函数设计：针对TSP问题，设计更为合理的适应度函数，将城市间的距离和路径长度综合考虑，提高搜索效率。
3. 选择操作：采用多种选择策略相结合的方式，如轮盘赌选择、锦标赛选择等，提高种群的多样性。
4. 交叉操作：引入多种交叉方式，如单点交叉、多点交叉和均匀交叉等，提高算法的搜索能力。
5. 变异操作：在变异过程中引入扰动机制，增加种群的活跃度，避免陷入局部最优解。
五、实验设计与结果分析为了验证改进的遗传算法在TSP问题中的有效性，本文设计了多组实验。
实验中，我们采用了不同规模的TSP问题实例（如城市数量从几十到几百不等），并与其他遗传算法进行比较。
实验结果表明，改进的遗传算法在TSP问题上具有更好的性能。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。
第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。
具体程序流程图见下图所示：
图1遗传算法流程图
四、优化过程
1.第一题
图2Rosen brock函数图像
图3遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
从上面的寻优结果可以看出，模拟退火算法解决了本例中遗传算法寻优陷入局部最优解的问题，最终找到了Schaffer Function函数的全局唯一最优解 。
问题二：寻优速度
基本的遗传算法中产生优良个体的主要手段是同过交叉重组，但这样并不能保证产生新个体的速度，即迭代寻优的速度很慢，考虑到为了保证较高的精度，本文的基因编码分别是十位、十二位与十三位，那么对于二元函数，染色体的长度就是二十、二十四与二十六，因此可以在交叉重组时，将较长的染色体分为若干段，并对每一小段进行两两配对交叉重组，这样相当于每个染色体在一次的迭代过程中参与了几次交叉重组，大大加快了新个体的产生速度。本文即将染色体分为了两段，进行交叉重组（程序见附录），加快了寻优速度。
第三题变量的取值范围是[-4,4]，本文采取的是十三位数的编码，那么精度为：
2)解码：假设某一个个体的编码是 ，那么对应的解码公式为：
2.个体适应度评价
1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：
其中 是函数最小值估计。
2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即
其中 是函数的最大值估计。
3.复制、交叉、变异
1)比例算子：个体被选中并遗传到下一代的概率与个体的适应度成正比，本文采取的的赌轮盘选择法选，该方法较容易实现，易于编程。
2)交叉算子：交叉是遗传算法产生新个体的主要手段，通过交叉子代的基因值不同于父代，从而可以出现适应度更高的个体，本文采用的是单点交叉算子。
五、问题的发现与改进
1.问题一：局部最优解
从第三题的函数图像中可以看出，该函数有无限多个局部极大值点，只有一个全局最优点 ,此函数最导致峰周围有一圈脊，上面的取值均为0.990283。从上面的优化过程可以看出，当随机选定初始种群后，随着迭代次数的增加，种群最终都集中在了这一圈脊上，也就是寻优过程陷入了局部最优点，并没有找到函数的的最优点。对于遗传算法中的上述问题，我们采用的解决方案如下。
解决方法1：等值线法
初始种群的选取对函数能不能找到最优点有着重要的影响，本文通过分析函数的等值线缩小初始种群的随机产生范围，从而让种群朝着全局最优点进化。在Matlab下画出函数的等值线如下图：
图8目标函数的等值线图
从图中可以看出，以中心最优点为圆心，围绕着中心点分布着多条等值线，从中心的红色区域向外到蓝色区域，目标函数值先减小再增加最后又减小，所以本文以中间红色区域到蓝色区域中选取合适的等值线截面，并在该面上随机产生初始种群，这样可以有效防止迭代陷入局部最优解。改进后的寻优结果：
优化算法大作业
一、题目
本文利用遗传算法，依次完成下面三个目标函数的寻优：
1Generalized Rosen brock’s valley Function
2GeneralizedRastrigin'sFunction
3Schaffer’s Function
二、本文思路
遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法，本文利用遗传算法分别对上述三种函数进行全局寻优，具体思路如下：
图10模拟推过算法实现过程
相关参数选择为：
初始温度Temperature=30
步长因子StepFactor=0.002
容差Tolerance=1e-7
马可夫链长度MarkovLength=1000
衰减参数DecayScale=0.95
程序运行结果为（程序见附录）：
最优点函数取值
寻优过程如下：
图11模拟退火算法的寻优过程
3)变异算子：变异也是产生新个体的一种方法，对于遗传算法中二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将基因值变为1，反之，若原有的基因值为1，则变异操作将其变为0。
三、程序流程
对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：
第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；
图9改进后的遗传算法寻优过程
图6中的最终种群进化到了函数一圈“脊”上，但是这只是函数的局部最优点，而从图9可以清楚地看到，种群进化到最后都集中在了中心凸起点的附近，这也是函数的最大值点，可见改进后的遗传算法有效的解决了局部最优点的问题，顺利找到了函数的全局最优解。
解决方法2：模拟退火算法
模拟退火算法是模仿了自然界退火现象，利用了物理中固体物质的退火过程与一般问题的相似性，从某一初始温度开始，伴随着温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解，它能有效的克服寻优陷入局部最小值的优化方法。其具体算法原理本文不详述，只给出采用模拟退火算法的实现过程如下图所示：
1.编码与解码
1)编码：假设某一参数的取值范围是[umin,umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，编码的长度越长，对应的精度越高。
第一题变量的取值范围是[-2.048,2.048]，本文采取十位数的编码，那么精度为：
第二题变量的取值范围是[-5.12,5.12]，本文采取的是十二位数的编码，那么精度为：
第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；
第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；
第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；
第五步：确定个体适应度的ห้องสมุดไป่ตู้化评价方法，即确定出由目标函数值到个体适应度的转换规则；
2.第二题
图4：Rastrigin函数图像
图5：遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
3.第三题
图6Schaffer函数图像
图7遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。
第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。
具体程序流程图见下图所示：
图1遗传算法流程图
四、优化过程
1.第一题
图2Rosen brock函数图像
图3遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
从上面的寻优结果可以看出，模拟退火算法解决了本例中遗传算法寻优陷入局部最优解的问题，最终找到了Schaffer Function函数的全局唯一最优解 。
问题二：寻优速度
基本的遗传算法中产生优良个体的主要手段是同过交叉重组，但这样并不能保证产生新个体的速度，即迭代寻优的速度很慢，考虑到为了保证较高的精度，本文的基因编码分别是十位、十二位与十三位，那么对于二元函数，染色体的长度就是二十、二十四与二十六，因此可以在交叉重组时，将较长的染色体分为若干段，并对每一小段进行两两配对交叉重组，这样相当于每个染色体在一次的迭代过程中参与了几次交叉重组，大大加快了新个体的产生速度。本文即将染色体分为了两段，进行交叉重组（程序见附录），加快了寻优速度。
第三题变量的取值范围是[-4,4]，本文采取的是十三位数的编码，那么精度为：
2)解码：假设某一个个体的编码是 ，那么对应的解码公式为：
2.个体适应度评价
1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：
其中 是函数最小值估计。
2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即
其中 是函数的最大值估计。
3.复制、交叉、变异
1)比例算子：个体被选中并遗传到下一代的概率与个体的适应度成正比，本文采取的的赌轮盘选择法选，该方法较容易实现，易于编程。
2)交叉算子：交叉是遗传算法产生新个体的主要手段，通过交叉子代的基因值不同于父代，从而可以出现适应度更高的个体，本文采用的是单点交叉算子。
五、问题的发现与改进
1.问题一：局部最优解
从第三题的函数图像中可以看出，该函数有无限多个局部极大值点，只有一个全局最优点 ,此函数最导致峰周围有一圈脊，上面的取值均为0.990283。从上面的优化过程可以看出，当随机选定初始种群后，随着迭代次数的增加，种群最终都集中在了这一圈脊上，也就是寻优过程陷入了局部最优点，并没有找到函数的的最优点。对于遗传算法中的上述问题，我们采用的解决方案如下。
解决方法1：等值线法
初始种群的选取对函数能不能找到最优点有着重要的影响，本文通过分析函数的等值线缩小初始种群的随机产生范围，从而让种群朝着全局最优点进化。在Matlab下画出函数的等值线如下图：
图8目标函数的等值线图
从图中可以看出，以中心最优点为圆心，围绕着中心点分布着多条等值线，从中心的红色区域向外到蓝色区域，目标函数值先减小再增加最后又减小，所以本文以中间红色区域到蓝色区域中选取合适的等值线截面，并在该面上随机产生初始种群，这样可以有效防止迭代陷入局部最优解。改进后的寻优结果：
优化算法大作业
一、题目
本文利用遗传算法，依次完成下面三个目标函数的寻优：
1Generalized Rosen brock’s valley Function
2GeneralizedRastrigin'sFunction
3Schaffer’s Function
二、本文思路
遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法，本文利用遗传算法分别对上述三种函数进行全局寻优，具体思路如下：
图10模拟推过算法实现过程
相关参数选择为：
初始温度Temperature=30
步长因子StepFactor=0.002
容差Tolerance=1e-7
马可夫链长度MarkovLength=1000
衰减参数DecayScale=0.95
程序运行结果为（程序见附录）：
最优点函数取值
寻优过程如下：
图11模拟退火算法的寻优过程
3)变异算子：变异也是产生新个体的一种方法，对于遗传算法中二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将基因值变为1，反之，若原有的基因值为1，则变异操作将其变为0。
三、程序流程
对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：
第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；
图9改进后的遗传算法寻优过程
图6中的最终种群进化到了函数一圈“脊”上，但是这只是函数的局部最优点，而从图9可以清楚地看到，种群进化到最后都集中在了中心凸起点的附近，这也是函数的最大值点，可见改进后的遗传算法有效的解决了局部最优点的问题，顺利找到了函数的全局最优解。
解决方法2：模拟退火算法
模拟退火算法是模仿了自然界退火现象，利用了物理中固体物质的退火过程与一般问题的相似性，从某一初始温度开始，伴随着温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解，它能有效的克服寻优陷入局部最小值的优化方法。其具体算法原理本文不详述，只给出采用模拟退火算法的实现过程如下图所示：
1.编码与解码
1)编码：假设某一参数的取值范围是[umin,umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，编码的长度越长，对应的精度越高。
第一题变量的取值范围是[-2.048,2.048]，本文采取十位数的编码，那么精度为：
第二题变量的取值范围是[-5.12,5.12]，本文采取的是十二位数的编码，那么精度为：
第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；
第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；
第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；
第五步：确定个体适应度的ห้องสมุดไป่ตู้化评价方法，即确定出由目标函数值到个体适应度的转换规则；
2.第二题
图4：Rastrigin函数图像
图5：遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
3.第三题
图6Schaffer函数图像
图7遗传算法迭代寻优过程
程序运行结果如下：最优点函数取值
由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。