基于改进型自适应遗传算法求解设备多行布局问题

摘要/Abstract

摘要：

对面积不等、形状固定的设备多行布局问题，提出了自由换行布局策略和净行间距概念.构建了带逆向物流、净行间距的多目标组合优化数学模型.引入免疫系统群体多样性作为种群进化的标志的基础上，建立了改进的自适应遗传算法(Improved Adaptive Genetic Algorithm, IAGA)，实现了交叉概率和变异概率的非线性自适应调整.最后，对算法进行了实验对比分析.结果表明，所提出的算法能快速有效地获得问题的近似最优解，稳定性好，对解决设备多行布局组合优化问题具有实用价值.

关键词: 设备布局, 自由换行, 净行间距, 改进型自适应遗传算法

Abstract:

To solve the multi-line layout problems of equipment with unequal area and fixed shape, a free-for-line layout strategy was proposed and the definition of net line space was presented. An optimization mathematic model was built with the objectives of the reversed logistics and net line space. Based on introducing the immune system population diversity as sign of population evolution, an improved adaptive genetic algorithm (IAGA) was put forward. The nonlinear adaptive adjustment function was achieved for crossover and mutation probability. Finally, the proposed algorithm was compared and evaluated. The results indicate that the algorithm can quickly obtain the nearly optimal solution. It is very useful for solving the combinatorial optimization problems of the multiline layout problem of equipment.

Key words: layout of equipment, free-for-line layout, net line space, improved adaptive genetic algorithm

中图分类号:

TP 301.6

周娜，宓为建，徐子奇，舒帆. 基于改进型自适应遗传算法求解设备多行布局问题[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1924-1929.

ZHOU Na，MI Weijian，XU Ziqi,SHU Fan. Solution to Multi-Line Layout Problems of Equipment Based on Improved Adaptive Genetic Algorithm[J]. Journal of Shanghai Jiaotong University, 2013, 47(12): 1924-1929.

参考文献

［1］Abdullah K, Sadan K K. A newmixed integer programming formulation for facility layout design using flexible bays［J］. Operations Research Letters, 2006, 34(6)：660672.

［2］李波,马大奎,崔欣. 基于遗传算法的多目标设施定位方法［J］.中国机械工程，2008,19(7)：828833.

LI Bo, MA Dakui, CUI Xin. A multiobjectives method of facility location based on genetic algorithm ［J］. China Mechanical Engineering，2008,19(7)：828833.

［3］Amir S. A genetic algorithm with the heuristic procedure to solve the multiline layout problem［J］.Computers & Industrial Engineering，2012,62(4)：10551064.

［4］郭源源,王谦,梁峰.基于粒子群优化算法的车间布局设计［J］. 计算机集成制造系统，2012,18(11)：24762484.

GUO Yuanyuan, WANG Qian, LIANG Feng. Facility layout design based on particle swarm optimization［J］.Computer Integrated Manufacturing Systems， 2012,18(11)：24762484.

［5］阎树田,黄辉祥,吴文娟. 采用遗传算法的RMS设备布局设计及仿真［J］. 现代制造工程，2010(6)：4042,81.

YAN Shutian, HUANG Huixiang, WU Wenjuan. The design of facility layout of RMS based on genetic algorithm s and its simulation ［J］. Modern Manufacturing Engineering，2010(6)：4042,81.

［6］王占中,郑家彬,许洪国，等. 制造业物流缓存区布局优化［J］. 西南交通大学学报，2010,45(3)：476481.

WANG Zhanzhong, ZHENG Jiabin, XU Hongguo,et al.Optimization of logistics buffer zone layout in manufacturing industry［J］. Journal of Southwest Jiaotong Universit，2010,45(3)：476481.

［7］申建刚,王理,邱珮强. 基于遗传算法的设备布置优化算法［J］.北京航空航天大学学报，2009, 35(20)：12411244.

SHEN Jiangang, WANG Li, QIU Peiqiang. Optimization of machine layout based on genetic algorithm［J］. Journal of Beijing University of Aeronautics and Astronautics, 2009,35(20)：12411244.

［8］Raman D, Nagalingam S V, Gurd B W. A genetic algorithm and queuing theory based methodology for facilities layout problem［J］. International Journal of Production Research, 2009，47(20)：56115635.

［9］Ozcelik F, Islier A A. Generalization of unidirectional loop layout problem and solution by a genetic algorithm［J］. International Journal of Production Research, 2011,49(3)：747764.

［10］Liu X B, Sun X M. A multiimproved genetic algorithm for facility layout optimization based on slicing tree［J］. International Journal of Production Research, 2012,50 (18)：51735180.

［11］项彬彬,陈卫东,亓利伟, 等. 基于遗传算法的机器人作业单元布局优化［J］.上海交通大学学报, 2008, 42(10)：16971701.

XIANG Binbin, CHEN Weidong, QI Liwei,et al. Robot workcell layout optimization based on genetic algorithm［J］. Journal of Shanghai Jiaotong University， 2008, 42(10)：16971701.

［12 ］Zafer B. Adaptive genetic algorithms applied to dynamic multiobjective problems ［J］.Applied Soft Computing, 2007, 7(3)：791799

［13］申建刚,夏国平,邱珮强. 基于遗传算法和虚拟现实的施工设备布置系统［J］. 计算机集成制造系统, 2009,15(10):19861993.

SHEN Jiangang, XIA Guoping, QIU Peiqiang. Construction facility layout system based on genetic algorithm and virtual reality［J］. Computer Integrated Manufacturing Systems， 2009,15(10):19861993.

［14］周娜,徐克林,郭爽. 基于遗传算法的车间布局多目标优化［J］. 工业工程， 2011,14(5):104109.

ZHOU Na, XU Kelin, GUO Shuang. Multiobjective optimization of workshop layout based on genetic algorithm［J］. Industrial Engineering，2011.14(5):104109.

［15］焦李成, 尚荣华, 马文萍，等. 多目标优化免疫算法理论和应用［M］. 北京：科学出版社,2010：5455.

[1]	邹志文，李桥，寇爱军. 传感器网络空间关键字近似Top-k查询算法[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1457-1460.
[2]	方鹏亚，常新龙，胡宽，张晓军. 基于区间不确定性的多学科可靠性设计[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1451-1456.
[3]	袁鑫攀1,盛鑫海1,龙军2,张祖平2,桂卫华2. 基于连接位Minwise Hash的三者相似性估计算法[J]. 上海交通大学学报（自然版）, 2014, 48(07): 936-941.
[4]	黎渊1, 蒋江2, 张民选1, 魏少军3 . 基于模拟退火算法的浮点转定点自动位宽优化工具[J]. 上海交通大学学报（自然版）, 2013, 47(01): 76-80.
[5]	姜梦稚1, 2, 赵风景2. 基于可计算函数的C模型互模拟性质[J]. 上海交通大学学报（自然版）, 2012, 46(04): 620-623.
[6]	曾敏,骆源. F2上两类向量深度的分布[J]. 上海交通大学学报（自然版）, 2008, 42(12): 2060-2064.
[7]	方鹏亚，常新龙，胡宽，张有宏. 基于渐近松弛的协同优化方法[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1896-1901.
[8]	杨伏洲，王海燕，申晓红，荆海霞. 基于时间反转的非均匀线列阵超指向性阵元分布模型[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1907-1910.
[9]	张志英1，林晨1，杨连生1,2，薛士枚3，刘建峰2. 面向分段涂装作业的混合流水车间调度[J]. 上海交通大学学报（自然版）, 2014, 48(03): 382-387.
[10]	朴昌浩1，黄质1，苏岭2，禄盛1. 基于角度分布的高维数据流异常点检测算法[J]. 上海交通大学学报（自然版）, 2014, 48(05): 647-652.
[11]	陈明，张丰，杜震洪，刘仁义. 环状分布平面点集的凸包快速生成算法[J]. 上海交通大学学报（自然版）, 2014, 48(05): 658-662.
[12]	黄炫圭. 小边概率条件下较小植入团的算法[J]. 上海交通大学学报, 2017, 51(10): 1202-1206.