摘要
矩形件优化排料是一类具有NP完全难度的组合优化问题。有关的优化问题可用与或树来描述,这样就把矩形件优化排料问题变换为寻找一棵面积比率最大的二叉树。用ACS算法实现这种树搜索,是把一定数量的人工蚂蚁分布在与或树的根节点,人工蚂蚁间通过使用信息素相互交流,完成从与或树到二叉树的选择,从而得到矩形件优化排料问题的优化解。
The optimal layout for rectangular part is a NP-complete combinatorial optimization problem. This optimal problem is represented by an AND/OR tree and then its optimal objective becomes to find the binary tree whose ratio of the area is maximum. To implement this kind of tree search using ant colony system algorithm, a number of artificial ants are distributed on the root of the AND/OR tree and communicate with one another through the pheromone trails which are a form of the long-term memory guiding the future exploration of the AND/OR tree, with which the optimal solution of the rectangular part optimal layout could be obtained.
出处
《计算机工程与设计》
CSCD
北大核心
2006年第2期356-358,共3页
Computer Engineering and Design
关键词
矩形件优化排料
ACS算法
树搜索
rectangular parts optimal layout
ant colony system （ACS） algorithm
tree search
