交互式优化设计方法综述＊

霍军周，张 旭，邓立营

（1.大连理工大学 机 械工程学院，辽宁 大连 116024；2.北方重工集团有限公司，辽宁 沈阳 110141）

0 引言

调度、路径规划、布局设计和排样等复杂优化问题广泛地存在于工业生产中，此类问题在数学上属于NP问题，很难找到全局最优解，过去多数研究集中于自动化设计方法，而忽略了作为主体的人在此类问题求解中所应起到的作用。钱学森、戴汝为提出人机结合［1，2］和 Lenat等提出的人机合作［3］思想都表明了人在求解复杂工程问题中的重要性。

对于复杂机械工程系统优化设计问题，建立严格数学模型相当困难，且往往很难达到工程实用化，而人类经验知识及“灵感”（创新能力）在求解该复杂问题时具有不可替代的作用，这使得用交互式优化方法求解复杂优化设计问题成为研究的热点。

本文综述了国内外目前常用的交互式优化方法，并依据人作用于优化问题侧重点的不同，将交互式优化方法分成交互式的动态修正模型法、交互式的方案评价法和多方式混合交互方法，分别讨论了这几类交互式优化方法的特点及应用范围。

1 交互式的动态修正模型法

多数复杂优化设计问题常常处于概念设计阶段，还无法完全明确设计意图，因此一些学者研究了在优化过程中动态地交互式改变优化求解模型，如一个商业的优化工具Optdes X允许设计者在优化过程中动态地改变优化模型，如改变设计变量、设计目标和约束等，但是其可视化的只是一些数值信息，且设计者没有重新编程和编译是不能改变整个设计问题的。

文献［4，5］设计的基于约束系统将图形绘制引入到系统中，设计者通过一种直觉的图形绘制方式来表示几何约束或者拓扑约束以便将后来的操作约束到有用的设计空间中。但上述研究尚处于初步研究阶段，似乎还未从根本上解决模型修正或重建问题。

2 交互式的方案评价法

工程实际优化问题中有一些无法或难以用现有数学手段形式化为计算机可以接受的优化目标或约束条件，因此对于算法生成的此类优化问题方案无法通过算法进行定量地评价，此外，工程实际中的多数优化问题属多目标优化问题，存在多目标参数确定的困难，此时可以将这部分算法难以胜任的工作交与人来做，人根据经验和工程实际要求，可以合理地反映此类设计要求和意图并有助于产生更具工程实用价值的设计方案。

此类方法最早研究的是人参与演化算法的适应度函数的评价，如单纯利用人的经验确定演化算法个体的适应度函数值［6］。文献［7］提出了一种交互式的元启发式演化方法来求解多目标组合优化问题，决策者利用演化方法提供的解进行比较来决定新产生解的适应度函数值来引导算法搜索到决策者期望的解，上述方法将演化算法个体的适应度函数值通过人工方式定量化。

工程实际中还有一些难以定量化评价的优化设计问题，如服装设计、音乐创作等领域，文献［8，9］研究了交互式演化算法，其借助演化算法的优化进程调度框架，通过将算法难以处理的部分工作（如方案评价）委托给人，从而将演化算法的应用领域扩展到一些难以定量化评价、甚至难以定量化描述的设计领域。以交互式遗传算法在服装设计中的应用为例，它通过对服装设计中的关键设计要素进行数值编码可以实现设计方案的表达，也可以通过对这些数值编码的数学操作实现新的设计方案的生成，但却难以对服装设计方案的评价给出严格的数学标准。于是，就将新解（设计方案）的评价委托给设计人员，从设计人员那里不断获取算法运行所需的评价信息，从而使演化算法能够正常运行，实现服装的创新（优化）设计。但是这种方法应用的好坏往往取决于设计者的偏好。文献［10～13］研究了基于决策者偏好的交互式优化模型及求解方法，它既能够反映决策者的满意度，又能够得到稳健的最优解。文献［14］研究了人机结合效率的高低，通过实验研究表明：学习对象层次不同，其人机结合效率存在着明显差异。

上述交互式方案评价的研究为我们处理算法难以评价的一类优化问题以及发挥人的创新能力提供了一种思路。

3 多方式混合交互方法

随着对交互式优化研究的深入，为了在交互式优化系统中使人更有效、更自然地发挥作用，众多学者研究了前述多方式的混合方法。

文献［15］的交互式方法中，人除了可以对算法进行引导，还可以在算法运行当中添加问题约束。文献［16］应用交互式遗传算法进行工艺品布局问题求解，让设计师从适应度评价和人工方案设计等方面进行人机交互。

对于某些特定的优化问题，需要强调多人的经验以及交流的作用，文献［17］研究了基于人的演化算法，将设计方案的表达、新解的产生和解的评价全部委托给多个设计人员（人类Agent），算法只负责优化进程调度和数据管理，这样一来，它将“优化的对象扩展到了诸如‘什么是知识？’这类可以以自然语言来表达的问题（如果称得上‘优化’问题的话）”。这更倾向于将演化计算作为一种以知识获取、利用和生产为核心的人机集成系统的组织形式［18］。但是，上述多人混合交互式方法往往存在需解决的“冲突”问题。文献［19］从工程应用角度综述人机交互若干关键支持技术。

相对于单一的交互方式，上述多方式混合交互方法研究可以让设计者有更多的选择权，可以使设计者更自然地进行人机交互，同时也使得复杂优化问题的表达更自然、更实用。

4 交互式优化方法的研究方向

目前，交互式优化方法的研究仍处于发展阶段，该方法多是求解一定程度上简化的优化模型。对于解决工程复杂优化问题，还有以下几个方面有待深入研究和探讨：

（1）加深对人机交互理论和工程优化问题本质的认识，从而能从本质上区分人和计算机的优势，目前的多数研究侧重于人与算法交互的方式，而Scott［20］研究了人和算法各自的优势，并指出若要在此方面取得进一步进展，必须对作为个体的人进行严格的研究分析以及研究基于人的假设条件。

（2）基于知识工程（knowledge based engineering，KBF）可以将前人或众多专家的经验集成，以实现知识型资源的重用，目前大型三维CAD商业软件多开发了相应的知识处理模块和应用模块，因此研究广义人机交互、知识工程和三维CAD软件集成也是一个值得重视的问题。

5 结论

本文综述了国内外目前常用的交互式优化方法，并依据人作用于优化模型算法时对优化问题侧重点的不同，将交互式优化方法分成交互式的动态修正模型法、交互式的方案评价法和多方式混合交互方法。分别讨论了这几类交互式优化方法的特点，最后指出了交互优化设计中尚有待深入研究的问题。

［1］ 钱学森，于景元，戴汝为.一个科学的新领域——开放的复杂巨系统及其方法论［J］.自然杂志，1990，13（1）：3－10.

［2］ 戴汝为.“人机结合”大成智慧［J］.模式识别与人工智能，1994，7（3）：181－190.

［3］ Lenat D B，Feigenbaum E A.On the thresholds of knowledge［G］／／Proceedings of the International Workshop on Artificial Intelligence for Industrial Applications.Japan：IEEE，1988：291－300.

［4］ Gleicher M，Witkin A.Drawing with constraints［J］.Visual Computer，1994，11：39－51.

［5］ Ryall K，Mar ks J，Shieber S.Glide：an interactive system f or graph drawing［J］.Lecture Notes in Computer Science，1997，1190：387－394.

［6］ Takagi H.Interactive evolutionary computation：system optimization based on human subjective evaluation［C］／／IEEE Int Confon Intelligent Engineering Systems.Austria：IEEE，1998：1－6.

［7］ Selcen Phelps，Murat Kqsalan.An interactive evolutionary metaheuristic for multiobjective combinatorial optimization［J］.Management Science，2003，49（12）：1726－1738.

［8］ Sung－Bae Cho.Towards creative evolutionary systems with interactive algorithm ［J］.Applied Intelligence，2002，16（1）：129－138.

［9］ Handy Haupt，Suo Ellen Haupt.The creative use of genetic algorithm［J］.IEEE Potentials，2000，19（2）：26－29.

［10］ 万中，郝爱云，孟福直，等.随机环境下多目标设计优化问题的交互式算法［J］.湖南大学学报，2010，37（8）：83－86.

［11］ Pardo M J，Fuente D.Design of a fuzzy finite capacity queuing model based on the degree of customer satisfaction：analysis and fuzzy optimization［J］.Fuzzy Sets and Systems，2008，150：3313－3332.

［12］ 张旭，孙伟，许焕卫.交互式模糊稳健优化设计及其应用［J］.大连理工大学学报，2010，50（5）：672－676.

［13］ 边晶梅，朱浮声，崔可民.混凝土桥面板长期维修优化与交互式遗传算法［J］.沈阳建筑大学学报，2009，25（3）：511－516.

［14］ 庞志兵，齐根华，侯润峰.人机结合效率的实验研究［J］.人类工效学，2005，11（2）：10－12.

［15］ Hugo A D，Do Nascimento，Peter Eades.User hints for directed graph drawing［J］.Lecture Notes in Computer Science，2002：205－219.

［16］ 黄琦，孙守迁，潘云鹤.一种基于遗传算法的工艺品布局求解算法［J］.计算机辅助设计与图形学学报，2002，14（10）：982－987.

［17］ Kosorukoff A.Hu man based genetic algorithm［C］／／2001 IEEE Inter national Conference on Systems，Man，and Cybernetics.Tucson：IEEE，2001：3464－3469.

［18］ Kosoruko A，Goldberg D.Evolutionary computation as a form of organization［G］／／Proceedings of t he Genetic and Evolutionary Computation Conference.［s.l.］：［s.n.］，2002：965－972.

［19］ 滕弘飞，王奕首，史彦军.人机结合的关键支持技术［J］.机械工程学报，2006，42（11）：1－9.

［20］ Scott S，Lesh N，Klau G W.Investigating human－computer optimization［C］／／ ACM Conference on Human Factors in Computing Systems.New York：ACM，2002.