2012年数学建模之遗传算法(改进与应用).ppt

遗传算法（改进与应用） 国防科技大学理学院数学系 成礼智 2011年夏季学期数学建模竞赛讲座 Y3. 两个考生的“面试组”中有两位或三位老师相同的情形尽量的少； Y4. 任意两位面试老师面试的两个学生集合中，出现相同学生的人数尽量的少。 请回答如下问题： 问题一：设考生数N已知，在满足Y2条件下，说明聘请老师数M至少分别应为多大，才能做到任两位学生之间都没有两位以及三位面试老师相同的情形。 问题二：请根据Y1～Y4的要求建立学生与面试老师之间合理的分配模型，并就N＝379，M＝24的情形给出具体的分配方案（每位老师面试哪些学生）及该方案满足Y1～Y4这些要求的情况。 问题三：假设面试老师中理科与文科的老师各占一半，并且要求每位学生接受两位文科与两位理科老师的面试，请在此假设下分别回答问题一与问题二。 问题四：请讨论考生与面试老师之间分配的均匀性和面试公平性的关系。为了保证面试的公平性，除了组织者提出的要求外，你们认为还有哪些重要因素需要考虑，试给出新的分配方案或建议。 遗传算法与模拟退火算法的比较 混合遗传算法算例 （见word文档：遗传算法与模拟比较与算例） ★求解线性约束优化问题的遗传算法 例：7×7运输规划问题 对于约束 ，个体染色体表示 为（v11,…,v77），其约束违反度定义为： 2. 遗传算法的应用 智能优化计算 2.1 解带约束的函数优化问题 ★求解线性约束优化问题的遗传算法 例：7×7运输规划问题 (费用参数表) 对于函数A，取S＝2，对于函数B、E和F，取S＝5。 2. 遗传算法的应用 智能优化计算 2.1 解带约束的函数优化问题 38 1000 27 0 60 54 62 20 42 47 0 27 98 67 93 20 35 0 47 1000 67 1000 77 20 20 25 28 27 cij 1000 50 21 0 20 48 17 0 21 20 25 0 17 50 20 0 25 48 1000 26 35 67 1000 77 25 42 98 67 93 26 38 60 54 62 23 ★求解线性约束优化问题的遗传算法 例：7×7运输规划问题 消除多余变量： 可以消除13个变量，x11, x12,…, x17, x21, x31, x41, x51, x61, x71，其余36个变量设定为y1,y2,…,y36 2. 遗传算法的应用 智能优化计算 2.1 解带约束的函数优化问题 ★求解线性约束优化问题的遗传算法 例：7×7运输规划问题 将原规划问题转化为： 2. 遗传算法的应用 智能优化计算 2.1 求解带约束的函数优化问题 ★求解线性约束优化问题的遗传算法 例：7×7运输规划问题 采用的参数：种群大小40，均匀变异概率0.08，边界变异概率0.03，非均匀变异概率0.07，简单交叉概率0.10，单一算术概率0.10，整体算术概率0.10，运行代数8000。 2. 遗传算法的应用 智能优化计算 2.1 解带约束的函数优化问题