遗传算法简单实例.pptVIP

遗传算法(GA)的肇始 “ 活的有机体是解决问题的专家。它们所表现出来的各种才能足以使最好的计算机程序自惭形秽。这种现象尤其令计算机科学家们感到痛楚。计算机科学家们为了某种算法可能花费数月乃至数年的脑力劳动，而有机体则能通过进化和自然选择这样一种显然并非定向进行的机制获得这种能力。” --- John Holland 遗传算法的思想 Darwin的进化论 ---- “自然选择、适者生存” 特定环境的考验 种群中个体的选择 种群中的交叉繁殖 种群中个体的变异 上述操作反复执行，个体逐渐优化 遗传算法的一个实例 求解方程： 将方程求解问题转化为生存问题： 解一定在[0,10]之间，将区间[0,10]划分成若干个小区间，设想每个小区间为一个生物个体，使下列表达式最小的个体有 最好的生存能力，该个体即为解。 遗传算法的一个实例 如何找到这个最优个体？ 可通过 Darwin 的进化论由初始个体经过代代演化，逐渐进化出来。 如何将生物进化的操作转化为计算机可以执行的操作？ 通过编码表征生物个体，则生物之间的演化转化为编码的变化。 步骤一：初始化 个体编码：(假定要求小数点后两位) 将[0,10]划分为1024个小区间 个体 1 0000000000 个体 2 0000000001 个体 3 0000000010 …… 个体 1024 1111111111 种群初始化： 随机生成m个10位二进制串 步骤二：选择 定义适应度函数： 选择（适应度较大的个体） 步骤三：交叉 选中的优势个体进行交叉 ----- 由父个体生成子个体 步骤四：变异 变异操作 在个体中随机选择一位，改变该位的值 步骤五 反复执行步骤二、三、四并记录最优个体（适应度最大的个体） 程序结束时，最优个体即为所求解 程序结束的判定 根据循环次数 根据最大适应度 根据种群中相同个体数与总个体数的比值 遗传算法各步骤的评价 选择 --- 优胜劣汰 选择操作为种群提供了演进的方向 交叉 --- 优优组合 交叉操作的作用在于汇集散布于不同 个体间的局部优势模式 变异 --- 寻找新模式 变异操作是种群向外扩展的触角(随机) 好的变异将保留，坏的淘汰 遗传算法的总体评价 优点 解决问题的方法具有普适性 全局收敛性（依概率收敛） 能解决的问题范围很广 不足 求得的解为近似的数值解 对于经典数学可以解决的问题，效率较低 遗传算法的适应度函数 求函数的全局极小值 取 的初始区间，例如：[-10,10] 将此区间分为1024个小区间，然后编码 若求全局极大值(且为正)，可直接取函数值 为其适应度值，据此作概率选择； 若求全局极小值(且为正)，可取函数值的倒 数为其适应度值，据此作概率选择。 若不全为负，可统一加上一个正数，使为正。 TSP问题的遗传算法求解 步骤一：个体编码及种群初始化 步骤二：适应度选择 步骤三：交叉操作 步骤四：变异操作 步骤五：重复二、三、四步，直至结束 令城市(点)数目为 N 步骤一：初始化 个体编码 取长度为N的数字串，串中数字互不重复，取值范围为[1,N]之间的整数。则每一个数字串代表一个个体，个体中数字出现的位置表征路径中城市出现的顺序。 初始种群 令种群中有 M 个个体，可随机产生 M 个数字 串构成初始种群。例如： 将数字串 1234…N 上的数字进行随机的交换 步骤二：适应度选择 适应度的计算 步骤三：交叉操作 TSP中交叉算子的特点 要保证生成的解为有效解 从一个父个体中随机选取一段子串A，在另一个父个体中将A中出现的数字去掉形成串B，AB为一个子串 步骤四：变异操作 常用的变异操作： 随机选取两个相邻位置的数字，交换其顺序。 51243(5) 51234(5) 步骤五： 反复执行步骤二、三、四 结束判定 循环执行 G 次 (例如 G=500) 后 当最优个体的总路径长度小于预期时 中国各省会城市的运行结果 12345(1) 32154(3) 相同父个体交叉 34215(3) 15234(1) 不同子个体，且和父个体不同 4.1 遗传算法简