免疫算法实例

智能控制课智能控制课程综合报告程综合报告 学学 院院自动化学院 专专 业业控制科学与工程 学学 号号 学生姓名学生姓名 指导教师指导教师 2016 年 6 月 7 日 基于免疫优化算法的物流中心选址基于免疫优化算法的物流中心选址 1 建立模型 建立模型 在物流配送中心选址模型中做如下假设 1 配送中心的规模容量总可以满足需求点需求 并由其配送辐射范围内的需 求量确定 2 一个需求点仅由一个配送中心供应 3 不考虑工厂到配送中心的运输费用 然后要从 n 个需求点中找出配送中心 并向需求点配送物品 目标函数是 各配送中心到需求点的需求量和距离的乘积之和最小 目标函数如下 2 问题的求解 问题的求解 2 1 算法的实现步骤 算法的实现步骤 1 产生初始种群 2 对上述群体中各个抗体进行评价 3 形成父代群体 4 判断是否满足条件 是则结束 反之 则继续下一步操作 5 新种群的产生 6 转去执行步骤 2 2 2 流程图如图流程图如图 1 1 ijiji ZdwF 图 1 1 算法流程图 2 3 初始群体的产生初始群体的产生 如果记忆库非空 则初始抗体群从记忆库中生成 否则 在可行解空间随 机产生初始抗体群 此处 采用简单的编码方式 每个选址方案可形成一个长度 为 P 的抗体 P 表示配送中心的数量 每个抗体代表被选为配送中心的需求点 的序列 如 考虑包含 31 个需求点的问题 从中选取 6 个作为配送中心 抗体 2 7 15 21 29 11 代表一个可行解 2 4 解的多样性评价 解的多样性评价 1 抗体与抗原之间的亲和力 表示新的目标函数 分母的第二项表示对违反距离约束的解给予惩罚 C 取比较大的正数 2 抗体与抗体之间的亲和力 其反映抗体之间的相似程度 此处借鉴 Forrest 等人提出的 R 位连续方法 计算抗体之间的亲和力 两个个体有至少 R 位编码相同则两种抗体近似相同 0 1min 1 F 1 v v ijijiji ZCZdw A ijiji ZdwF v F L k sv sv S 其中 k 表示抗体 v 和抗体 s 之间相同的位数 L 为抗体的总长 例如 两 个抗体 2 7 15 21 5 11 15 8 14 26 5 2 经比较有 3 个相同则亲和度为 0 5 3 抗体浓度 4 期望繁殖概率 在种群中 每个个体的期望繁殖概率与抗体与抗原之间的亲和力 A 和抗体 浓度共同决定 是常数 可见个体的适应度越高 则期望繁殖率越大 个体的浓度越大 则期望繁殖率越大 这样就鼓励了高适应度个体 抑制了高浓度个体 2 5 免疫操作免疫操作 1 选择 按照轮盘赌机制进行选择操作 个体被选择的概率即为期望繁殖概 率 2 交叉 采用单点交叉法进行交叉操作 3 变异 采用随机变异位进行变异操作 3 模型的求解模型的求解 为证明算法的有效性和可行性 采集了 31 个城市的坐标 每个用户的位置 以及物资需求进行仿真 根据配送中心选址模型 按照免疫算法流程对该例求解 参数设置 种群规模 50 记忆库容量 10 迭代次数 100 交叉率 0 5 Ni sv v S N 1 C 他他0 S1 S v s v s T v v v v 1P C C A A 他他 变异概率 0 4 多样性评价参数 0 95 4 matlab 仿真结果仿真结果 图 4 1 适应度曲线 图 4 2 选址方案 最后 结果选址方案是 5 25 18 9 12 27 如图中所标 可以看出免疫算法有 较好的收敛性 5 算法应用展望算法应用展望 免疫算法能够增强系统的鲁棒性 从选址的模型上看 免疫算法就是解决 了最优花费的一个聚类 因此 希望在后期的研究中能应用在多模式分类问题 上 附录 Matlab 求解的主程序 算法基本参数 sizepop 50 种群规模 overbest 10 记忆库容量 MAXGEN 100 迭代次数 pcross 0 5 交叉概率 pmutation 0 4 变异概率 ps 0 95 多样性评价参数 length 6 配送中心数 M sizepop overbest step1 识别抗原 将种群信息定义为一个结构体 individuals struct fitness zeros 1 M concentration zeros 1 M excellence zeros 1 M chrom step2 产生初始抗体群 individuals chrom popinit M length trace 记录每代最个体优适应度和平均适应度 迭代寻优 for iii 1 MAXGEN step3 抗体群多样性评价 for i 1 M individuals fitness i fitness individuals chrom i 抗体与抗原亲和度 适应度 值 计算 individuals concentration i concentration i M individuals 抗体浓度计算 end 综合亲和度和浓度评价抗体优秀程度 得出繁殖概率 individuals excellence excellence individuals M ps 记录当代最佳个体和种群平均适应度 best index min individuals fitness 找出最优适应度 bestchrom individuals chrom index 找出最优个体 average mean individuals fitness 计算平均适应度 trace trace best average 记录 step4 根据 excellence 形成父代群 更新记忆库 加入精英保留策略 可由 s 控 制 bestindividuals bestselect individuals M overbest 更新记忆库 individuals bestselect individuals M sizepop 形成父代群 step5 选择 交叉 变异操作 再加入记忆库中抗体 产生新种群 individuals Select individuals sizepop 选择 individuals chrom Cross pcross individuals chrom sizepop length 交叉 individuals chrom Mutation pmutation individuals chrom sizepop length 变异 individuals incorporate individuals sizepop bestindividuals overbest 加入记忆库中抗体 end 画出免疫算法收敛曲线 figure 1 plot trace 1 r linewidth 2 hold on plot trace 2 linewidth 2 legend 最优适应度值 平均适应度值 grid on title 免疫算法收敛曲线 fontsize 12 xlabel 迭代次数 fontsize 12 ylabel 适应度值 fontsize 12 画出配送中心选址图 城市坐标 city coordinate 1304 2312 3639 1315 4177 2244 3712 1399 3488 1535 3326 1556 3238 1229 4196 1044 4312 790 4386 570 3007 1970 2562 1756 2788 1491 2381 1676 1332 695 3715 1678 3918 2179 4061 2370 3780 22 12 3676 2578 4029 2838 4263 2931 3429 1908 3507 2376 3394 2643 3439 3201 2935 3240 3140 3550 2545 2 357 2778 2826 2370 2975 carge 20 90 90 60 70 70 40 90 90 70 60 40 40 40 20 80 90 70 100 50 50 50 80 70 80 40 40 60 7 0 50 30 找出最近配送点 for i 1 31 distance i dist city coordinate i city coordinate bestchrom end a b min distance index cell 1 length for i 1 length 计算各个派送点的地址 index i find b i end figure 2 title 最优规划派送路线 cargox city coordinate bestchrom 1 cargoy city coordinate bestchrom 2 plot cargox cargoy rs LineWidth 2 MarkerEdgeColor r MarkerFaceColor b MarkerSize 20 hold on plot city coordinate 1 city coordinate 2 o LineWidth 2 MarkerEdgeColor k MarkerFac