导引式局部搜索在一类过度约束VRP中的应用

针对一类带时间窗口和容量约束的车辆路线问题(VRP),给出了在过度约束即不存在满足所有约束的可行解的情况下,能够最小化约束违反成本的一种新颖的导引式局部搜索(GLS)算法。该算法通过不断动态修改原问题的目标函数,既保留了局部搜索算法的高效率,又有效克服了局部极小解的局限性,因而能够较快地返回一个满意解。求解示例表明,该算法在求解此类问题时,性能要优于常用的禁忌搜索算法。     

求解模糊目标／资源问题的拟人化算法

介绍一种求解具有模糊资源约束线性规则问题的拟人化算法,它将模糊控制算法嵌在遗传算法之中可以解出一个模糊优解,取代了以往利用单纯形法求解模糊线性规划得到的唯一最优解,通过例子,可以看出该算法能得到一个满意度很高的解．     

基于二层规划的委托代理协调问题

考虑不对称信息条件下的委托代理问题,结合不适定二层规划的理论,给出了不适定委托代理问题的定义. 针对后者的乐观模型,利用一种模糊交互式协调算法进行求解,最终获得了一个委托人与代理人均可以接受的满意契约,从而达到了双方共赢的目的. 最后通过一个算例说明了所设计算法的合理性与可操作性.     

线性-二次双层规划的满意解与基于LP与NLP过程的算法

对线性-二次双层规划(简称LQP)模型提出求满意解的直接搜索方法.得到了基于LP与NLP过程来协调LQP上下层满意度与求满意解的算法.数值计算实例表明,算法得到的满意解较之传统最优解更有效.     

基于遗传算法的一类武器目标分配方法研究

针对联合作战的武器目标分配问题,建立了资源受限条件下的多组武器目标分配数学模型,并研究了用遗传算法求解模型的方法.该遗传算法通过设计一种满足约束条件的染色体编码格式,把求解问题转化为无约束的组合优化表现形式,从而可以利用单点随机定位算术交叉和变异运算以及精华选择策略来求解.仿真计算结果表明了模型和所提算法的有效性.     

不确定计划数的轧制批量计划的模型和算法

根据热轧生产工艺将热轧生产批量计划归结为不确定车辆数的车辆路径问题 (VRP) ,考虑了轧制计划中钢板宽度的反跳和相同宽度钢板的总长度约束 ,在轧制作业计划数不确定的情况下 ,把组批和排序有机地结合起来 ,并用遗传算法和禁忌搜索算法相结合的混合算法对问题进行求解 ,实验结果表明算法获得的最好解、平均负荷率和计算成本都比较令人满意 .     

考虑延期交货、转包和非减库存能力约束的单产品批量模型

研究了一个非减库存能力约束下的允许延期交货和转包的单产品动态批量问题.引入子计划概念,通过先求解所有可能的子计划,再基于动态规划搜索子计划的最优组合,得到问题的最优解.给出了所有子计划的通用数学描述,并通过松弛正生产量约束将子计划的计算分成两个子问题;依据子问题和子计划最优解的性质,设计了求解子问题和重新集结松弛约束的多项式算法;在此基础上提出了一个复杂性为O(T4)的求解整个规划问题的多项式动态规划算法,这里T是规划时段上的周期数.最后通过数值试验测试了该算法的性能.     

Global convergence of a class of smooth penalty methods for semi-infinite programming

For the semi-infinite programming (SIP) problem, the authors first convert it into an equivalent nonlinear programming problem with only one inequality constraint by using an integral function, and then propose a smooth penalty method based on a class of smooth functions. The main feature of this method is that the global solution of the penalty function is not necessarily solved at each iteration, and under mild assumptions, the method is always feasible and efficient when the evaluation of the integral function is not very expensive. The global convergence property is obtained in the absence of any constraint qualifications, that is, any accumulation point of the sequence generated by the algorithm is the solution of the SIP. Moreover, the authors show a perturbation theorem of the method and obtain several interesting results. Furthermore, the authors show that all iterative points remain feasible after a finite number of iterations under the Mangasarian-Fromovitz constraint qualification. Finally, numerical results are given.     

基于蚂蚁算法的工件排序优化

工件排序是NP-hard问题，以丰田公司的汽车组装工件排序函数为目标函数，将蚂蚁算法应用于该问题求解。得到了蚂蚁算法的最优参数并获得满意可行解。算例证明，此算法优于目标追随法、遗传算法、模拟退火算法等算法。     

云环境下能耗优化的任务调度模型及虚拟机部署算法

云计算环境下,在满足用户服务级目标约束下,如何有效地进行资源分配调度,降低能耗,已成为不容忽略的关键问题.针对目前云计算系统服务资源分配调度问题在能耗方面的研究不足,提出一种能耗优化的资源分配调度体系架构,并基于此架构设计了一个满足实时用户SLA的能耗优化模型.该优化模型从系统级和部件级两个层次进行能耗优化.在系统级上,提出一种基于分组遗传算法最大限度降低系统空闲能耗的虚拟机部署算法,该算法将虚拟机和服务器之间的映射抽象为有约束的多维可变装箱问题;同时,在部件级上采用动态电压功率调整技术降低执行能耗,从而达到在满足用户需求的前提下,最大限度降低系统总能耗.仿真实验结果表明,该算法与同类算法相比,在相同条件下可有效降低云计算系统的能耗开销.     

用多目标进化算法求解二层规划双目标模型

传统单目标二层规划模型得到的最优解往往无法使上下级双方都满意.为此,通过在上层规划中同时考虑下级的目标函数,建立了原问题的上层为双目标规划的一个新模型.上下级可通过协商在该模型的Pareto-最优解集中找到双方满意解.对此模型设计了求解的多目标进化算法,用传统优化算法求解下层规划的单目标问题,而对上层的双目标规划问题则采用基于NSGA-Ⅱ的多目标进化算法求解.数值试验表明我们所提出的算法是有效的.     

Novel combinatorial algorithm for the problems of fuzzy grey multi-attribute group decision making

To study the fuzzy and grey information in the problems of multi-attribute group decision making, the basic concepts of both fuzzy grey numbers and grey interval numbers are given firstly, then a new model of fuzzy grey multi-attribute group decision making based on the theories of fuzzy mathematics and grey system is presented. Furthermore, the grey interval relative degree and deviation degree is defined, and both the optimistic algorithm of the grey interval relational degree and the algorithm of deviation degree minimization for solving this new model are also given. Finally, a decision making example to demonstrate the feasibility and rationality of this new method is given, and the results by using these two algorithms are uniform. Keywords: multi-attribute group decision making, fuzzy grey number, grey interval relational degree, deviation degree.     

几类非线性双层规划问题的混合遗传算法

针对几类具有特殊下层结构的非线性双层规划问题,提出了一种混合遗传算法。首先利用单纯形法的思想设计了新的杂交算子,使杂交个体与种群中好的个体组杂交,从而产生尽可能好的杂交后代;其次对每个相对固定的上层变量值x,通过计算下层最优解y来提高种群个体的可行性,并分析了下层最优解的计算误差对算法性能的影响;最后对于下层存在多个最优解的情况,通过求解一个单层规划,给出了下层最优解的选择方法。数值结果表明该算法是有效的。     

求解度约束最小生成树的单亲遗传算法

提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了它求解TSP问题的具体步骤和实例。     

Definition and Algorithms for Reliable Steiner Tree Problem

This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.     

基于目标偏离容忍水平的多目标交互式决策方法

提出了一种基于目标偏离容忍水平的多目标决策新方法．该方法充分考虑到了实际决策过程具有的目标多样性、主客观互动性等特点,根据目标希望水平和目标偏离容忍水平在原多目标问题的基础上构造辅助模型,通过求解辅助模型得到原问题的非劣解,并经过与决策者的反复交互将不同的目标偏离容忍水平整合入模型当中,最终得到满意解．本文的方法具有结构清晰、求解方便快捷、易于反映决策者偏好结构等优点．     

Dominance property based tabu search for single machine scheduling problems with family setups

The problem of minimizing the maximum lateness on a single machine with family setups is considered. To solve the problem, dominance property is studied and then introduced into the tabu search (TS) algorithm. With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space. The proposed algorithms are tested both on the randomly generated problems and on the real-life problems. Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.     

路网车流径路的满意优化

确定车流径路是铁路行车组织中的一项重要内容，其选择的优劣直接影响了区域铁路网的运输效率和经济效益。本文应用基于满意度原理的多目标优化方法，针对一般车流径路问题求解中追求目标最优的难度和不足，改进了在一定运输需求条件下对路网上双向、空重车流径路同时进行优化的多目标满意优化模型，并通过建立独立满意度和综合满意度来衡量优化解的品质。实例分析表明，对于实际的车流径路问题，满意优化方法比传统的最优化理论方法更适用和更有效。     

A Machine Learning Approach for Mechanism Selection in Complex Negotiations

Automated negotiation mechanisms can be helpful in contexts where users want to reach mutually satisfactory agreements about issues of shared interest, especially for complex problems with many interdependent issues. A variety of automated negotiation mechanisms have been proposed in the literature. The effectiveness of those mechanisms, however, may depend on the characteristics of the underlying negotiation problem (e.g. on the complexity of participant’s utility functions, as well as the degree of conflict between participants). While one mechanism may be a good choice for a negotiation problem, it may be a poor choice for another. In this paper, we pursue the problem of selecting the most effective negotiation mechanism given a particular problem by (1) defining a set of scenario metrics to capture the relevant features of negotiation problems, (2) evaluating the performance of a range of negotiation mechanisms on a diverse test suite of negotiation scenarios, (3) applying machine learning techniques to identify which mechanisms work best with which scenarios, and (4) demonstrating that using these classification rules for mechanism selection enables significantly better negotiation performance than any single mechanism alone.     

A two-level genetic algorithm for scheduling in assembly islands with fixed-position layouts

This paper focuses on the scheduling problem in assembly islands environment with fixed-position layouts. In such configuration, the product normally remains in one location for its entire manufacturing period while machines, materials and workers are moved to an assembly site called an assembly island. This production layout has some unique features such as moving assembly workers,tools and materials; limited space at assembly site; considerable distance between islands. The authors first give the definition and mathematical model for the scheduling problem and then propose a two-level genetic algorithm to obtain a near optimal solution to minimize the makespan. Experimental results show that this algorithm is effective. The performance analysis of the proposed algorithm indicates that it is more efficient in the airline or shipbuilding industry than in the machine or tool final assembly companies.