解优化问题的遗传分解.ppt

遗传算法解TSP问题 符号编码 TSP问题：给定一组n个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。 采用遗传算法解决这个问题 P=(1 2 4 3 8 5 9 6 7) 表示从城市1出发，依次经过城市2，4，3，8，5，9，6，7然后回到城市1。 现在常用的交叉策略为 部分匹配交叉(partally matched crossover)法 这种交叉策略是1985年Goldberg和Lingle提出的。首先依据均匀随机分布生成两个交叉点，定义这两点的区域为配对区域，并使用位置交换操作交换两个父串的配对区域;然后对于配对区域外出现的重复，依据配对区域内位置映射关系，逐一进行变换。 第二步 每个子循环位置（单循环除外）或选取A的符号或选取B的符号。 例：第二循环位置选B的符号，其他选A的符号，得 子代为 C=1 7 2 4 5 6 3 8 9 10 第四循环位置选B的符号，其他选A的符号，得 子代为 D=1 2 3 4 5 9 7 6 10 8 变异策略 变异是作用在单个染色体上。 1、位置的变异。随机选取染色体（字符串）上两个元，然后把第二个元放在第一个元之前。 2、次序的变异。随机选取染色体上两个元，然后变换它们的位置。 3、逆转变异。随机选取染色体上两个点，再将这两点内子串按反序插入到原位置中。如A的逆转点为3，6，经逆转后，变为： A=1 2 3 4 5 6 7 8 9 10 B=1 2 3 6 5 4 7 8 9 10 4、插入变异。从染色体中随机选取一个元，将此插入选择的插入点中对于上述A而言，若取插入元为5，插入点为2，则 B=1 2 5 3 4 6 7 8 9 10 最后给出解TSP问题的算法步骤。 第1步：从N个随机起点，产生N条路径，作为初始群体，以遍历次序作为代码。 第2步：求k代N个染色体的适应度（取路径长度的倒数）。 第3步：按某种策略选择N个染色体作为k+1代的父本。 第4步：对这些父本按某种策略进行交叉和变异运算，得N个k+1代得染色体。 第5步：求k+1代的极小解。若不收敛，则k=k+1,转第二步。若收敛，停止运算。 背包问题 (knapsack problem) 处理约束条件有两种方法：一种是用罚函数法改造目标函数，另一种是结合贪心算法改造染色体的解码过程。 1、罚函数法 适应度函数设计为 实际上，上述适应度函数基于一个考虑违背约束条件的惩罚处理，当问题规模很大时，尽管方法可行，但有哪些信誉好的足球投注网站效率很低，甚至很多情况下所得到的结果比贪心算法的结果差。 2、混合遗传算法 将启发式有哪些信誉好的足球投注网站算法“贪心算法”引入染色体解码过程中，具体做法为，对于那些不满足约束的染色体编码对应的个体，优先装入价值密度较大且编码值为1的物品，直至背包容量限制装不下为止，将未装入的物品编码值修正为0，形成个体新的染色体编码。 二重结构编码的遗传算法 1994年，坂和正南等提出一种改进编码方法（二重编码）来考虑约束条件的满足问题，并可以提高遗传算法的有哪些信誉好的足球投注网站效率。 二重结构编码方法如下图所示：个体表示的二重结构由变量码和附加码两行组成， 对于上述二重结构编码，交叉操作和变异操作的算子需要重新设计。 对于交叉操作，用通常的操作算子，产生新个体的上行附加码会出现重复。如果采用部分匹配交叉算子可以很好地解决这个问题。 值得注意的是，部分匹配操作中只是针对个体的上行附加码，子个体的下行变量码值仍根据其父个体中附加码与变量码的对应关系来确定。 5 7 2 8 1 6 4 3 1 0 0 1 1 0 1 0 5 7 6 2 4 8 1 3 1 0 0 0 1 1 1 0 7 1 6 2 4 8 3 5 1 1 0 1 0 0 1 1 7 4 2 8 1 6 3 5 1 0 1 0 1 0 1 1 对于变异操作，采用逆位遗传算子，对父个体随机选择两个变异点，两点间的上行附加码按相反顺序重新排列，而下行的变量码顺序不变。 7 2 5 8 4 1 6 3 1 0 0 1 1 0 1 0 7 2 6 1 4 8 5 3 1 0 0 1 1 0 1 0 针对电动帆航天器转移轨迹优化问题，提出了一种结合高斯伪谱法、遗传算法和序列二次规划算法的混合优化方法。这种混合优化方法通过遗传算法全局寻优获得高斯伪谱法中非线性规划问题的状态变量及控制变量初值，并采用序列二次规划算法在遗传算法获得初值的基础上进一步寻优。将上述混合优化方法应用于电动帆航天器轨迹优化问题中，并以火星探测任务、谷神星探测任务和太阳系边界探测任务为例进行了数学仿真。仿真结果表明，所提