第11期 2016年11月
组合机床与自动化加工技术
Modular Machine Tool & Automatic Manufacturing Technique
文章编号：10012265(2016)11013803
D0I:10.13462/j. cnki. mmtamt.2016.11.037
基于COIN算法的工艺原则布置优化
林巨广，荣海龙，汪洋
（合肥工业大学机械与汽车工程学院，合肥230009）
No.11 Nov.2016
矩阵模型代替传统遗传算法的交叉和变异，来更新产生新的子代种群，并在学习和优化过程中利用负相关学习与传统的正相关学习相结合的方法，保持了种群的多样性，提高了算法的收敛速度。最后通过运用该
算法解决焊装工厂的工艺原则布置问题，并以遗传算法做对比，验证了COIN算法的有效性。关键词：COIN算法；遗传算法；工艺原则布置
中图分类号：TH162；TG506
文献标识码：A
Optimization of Process Principle ArrangementBased on Coincidence Algorithm
LIN Ju-guang,RONG Hai-long,WANG Yang
(School of Machinery and Automobile Engineering, Hefei University of Technology, Hefei 230009, China) Abstract : To solve the problem of process principle arrangement,the Coincidence Algorithm which replaces the traditional genetic algorithm crossover and mutation with the joint probability matrix model uses both good and not-good solutions that is defined by fitness to generate the population in this paper. It maintains the diversity of the population and improves the convergence rate. Finally,using the Coincidence Algorithm to solve the problem of process principle arrangement,it verifies the validity of Coincidence Algorithm com pared with Genetic Algorithms
Key words: coincidence algorithm;genetic algorithms; process principle arrangement
引言 0
工艺原则布置对各类企业的生产成本和利润有很大的影响，汤普金斯的研究表明：企业的物料运输成本约占总成本的20%~50%，通过合理的布置设计，物流分析、规划，可以有效降低15%~30%，极大的提高了生产效率。工艺原则布置属于组合优化问题，目前实际生产中，最常用的解决方法是启发式方法：直接放置，然后两两调换，检验，修改，如此反复，直到满足条件。这种方法在求解规模比较小（N值较小）的布置问题时比较有效，随着规模不断增大，解空间呈指数增长，出现组合爆炸现象，求解困难。随着智能算法和计算机技术的发展，为解决组合优化问题产生了多种有效的算法，如遗传算法[2-5]、分布估计式算法[6-8] COIN算法[9-12]等智能算法通过随机抽取部分解，利用适应度函数进行分析，估计全局解的分布情况，进而进行全局搜索，在符合实际精度的条件下，快速、有效
的得出最优解。 1COIN算法
1.1COIN算法概述
COIN算法以传统的遗传算法（GeneticAlgorithm：收稿日期：2015-11-27
GA）和统计学为基础，并吸收了MIMIC（MutualInfor mationMaximizationforInput Clustering）算法的长处。遗传算法是由美国Michigan大学的Holland教授于 1969年提出，后经DeJongGoldberg等人归纳总结，形成的一类模拟进化算法。这种算法是模拟生物进化过程中优胜劣汰规则与群体内部染色体交叉、变异重组操作来处理复杂优化问题的启发式优化算法，在许多领域得到广泛的应用。但同样存在许多不足：易陷人局部最优、未成熟收敛、收敛性能差导致的耗费时间长。针对上述不足，文中提出的COIN算法避免了交叉、变异的重组操作，而是根据种群中优势群体的有效信息构造联合概率矩阵，通过联合概率矩阵来产生下-代种群，同时在更新联合概率矩阵过程中，将负相关与传统的正相关学习相结合，保持了物种的多样性，一定程度上避免了局部最优解的产生，加速了算法的收敛速度，有利于通过联合概率矩阵更有效的体现种群进化的方向。最后将该算法应用于解决焊装工厂的工艺原则布置问题，与遗传算法做对比，验证了该算法的有效性。COIN算法的流程图如图1所示。
[110109010国
2548号）
作者简介：林巨广（1963一），男，安徽霍邱人，合肥工业大学教授，博士生导师，博士，研究方向为汽车试验设备，智能制造，新能源汽车等领域研
；通讯作者：荣海龙（1990一），男，安徽单阳人，合肥工业大学硕士研究生，研究方向为计算机集成制造、智能制造，（E-mail）万底数据04@qq.com。