求解多目标最小生成树的一种新的遗传算法

在改进的非支配排序遗传算法（NSGA-II）的基础上,提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明：对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。     

A bi-objective integrated procurement,production, and distribution problem of a multi-echelon supply chain network design: A new tuned MOEA

Efficient management of supply chain (SC) requires systematic considerations of miscellaneous issues in its comprehensive version. In this paper, a multi-periodic structure is developed for a supply chain network design (SCND) involving suppliers, factories, distribution centers (DCs), and retailers. The nature of the logistic decisions is tactical that encompasses procurement of raw materials from suppliers, production of finished product at factories, distribution of finished product to retailers via DCs, and the storage of raw materials and end product at factories and DCs. Besides, to make the structure more comprehensive, a flow-shop scheduling model in manufacturing part of the SC is integrated in order to obtain optimal delivery time of the product that consists of the makespan and the ship time of the product to DCs via factories. Moreover, to make the model more realistic, shortage in the form of backorder can occur in each period. The two objectives are minimizing the total SC costs as well as minimizing the average tardiness of product to DCs. The obtained model is a bi-objective mixed-integer non-linear programming (MINLP) model that is shown to belong to NP-Hard class of the optimization problems. Thus, a novel algorithm, called multi-objective biogeography based optimization (MOBBO) with tuned parameters is presented to find a near-optimum solution. As there is no benchmark available in the literature, the parameter-tuned multi-objective simulated annealing algorithm (MOSA) and the popular non-dominated sorting genetic algorithm (NSGA-II) are developed to validate the results obtained and to evaluate the performance of MOBBO using randomly generated test instances.     

Bi-objective optimization of three echelon supply chain involving truck selection and loading using NSGA-II with heuristics algorithm

This paper models a three echelon supply chain distribution problem considering multiple time periods, multi-products and uncertain demands. To take the problem closer to reality we consider multiple truck types and focus on the truck selection and loading sub-problem. Truck selection is important because the quantity of goods to be transported varies regularly and also because different trucks have different hiring cost, mileage and speed. Truck loading is important when considering the optimal loading pattern of products having different shapes and sizes on trucks, which themselves have distinct loading capacities. The two objectives considered here are the cost and responsiveness of the supply chain. The distribution problem is solved using the non-dominated sorting genetic algorithm (NSGA-II). However, the genetic algorithms compromise the optimality of the sub-problems while optimizing the entire system. But the optimality of truck selection and loading sub-problem is non-compromisable in nature. Hence a heuristic algorithm is used innovatively along with the NSGA-II to produce much better solutions. To make our model more realistic, the distribution chain is modelled as a push–pull based supply chain having multiple time periods and using demand aggregation over time. Using a separate algorithm also gives the advantage of utilizing the difference in nature of the push and pull part of the supply chain by giving every individual truck different objectives. Real life like data is generated and the optimality gap between the heuristic and non-heuristic approach is calculated. A clear improvement in objectives can be seen while using the heuristic approach.     

多配送中心危险货物配送路径鲁棒优化

针对危险货物配送路径对不确定因素敏感度较高的问题,提出了鲁棒性可调的多配送中心危险货物配送路径鲁棒优化方法。首先,以最小化运输风险和最小化运输成本为目标,根据Bertsimas鲁棒离散优化理论,建立鲁棒优化模型;然后,在改进型强度Pareto进化算法（SPEA2）的基础上设计一种三段式编码的多目标遗传算法进行求解,在遗传操作中对不同染色体段分别采用不同的交叉和变异操作,有效避免了种群进化过程中不可行解的产生;最后,以庆阳市西峰区部分路网为例进行实证研究,并将配送方案落实到运输过程的路段中,形成具体的运输路径。研究结果表明：在多配送中心下,运用该鲁棒优化模型及算法,能快速得到具有较好鲁棒性的危险货物配送路径。     

面向胎盘植入产前诊断的医学语义特征提取算法

胎盘植入由于其临床特征隐匿,尚无一种敏感性、特异性高的产前诊断手段,因此文中将数据的特征提取方法引入胎盘植入产前诊断领域,从特征相关性的角度,提出胎盘植入有效医学语义的多目标特征优化问题,并给出求解该问题的一种改进的非支配排序遗传算法II( NSGA-II)。基于实际胎盘植入相关临床数据的计算结果表明,文中算法能从复杂的胎盘植入相关临床数据中提取具有胎盘植入有效语义的特征集合。经过接收者操作特征( ROC)曲线分析,提取的特征医学语义具有较高的诊断价值,可为产科医师研究胎盘植入的发病机制和及时产前诊断提供有效的辅助手段。文中研究还发现,一些临床生化检查指标具有重要作用,可作为胎盘植入产前诊断的有效依据。     

Two new meta-heuristics for a bi-objective supply chain scheduling problem in flow-shop environment

In this study, an integrated multi-objective production-distribution flow-shop scheduling problem will be taken into consideration with respect to two objective functions. The first objective function aims to minimize total weighted tardiness and make-span and the second objective function aims to minimize the summation of total weighted earliness, total weighted number of tardy jobs, inventory costs and total delivery costs. Firstly, a mathematical model is proposed for this problem. After that, two new meta-heuristic algorithms are developed in order to solve the problem. The first algorithm (HCMOPSO), is a multi-objective particle swarm optimization combined with a heuristic mutation operator, Gaussian membership function and a chaotic sequence and the second algorithm (HBNSGA-II), is a non-dominated sorting genetic algorithm II with a heuristic criterion for generation of initial population and a heuristic crossover operator. The proposed HCMOPSO and HBNSGA-II are tested and compared with a Non-dominated Sorting Genetic Algorithm II (NSGA-II), a Multi-Objective Particle Swarm Optimization (MOPSO) and two state-of-the-art algorithms from recent researches, by means of several comparing criteria. The computational experiments demonstrate the outperformance of the proposed HCMOPSO and HBNSGA-II.     

用带变异因子的QPSO算法解决Job-Shop调度问题

由于量子粒子群优化算法仍有可能会出现早熟现象,因此将变异机制引入量子粒子群优化算法以使算法跳出局部最优并增强其全局搜索能力,并将改进后的量子粒子群优化算法用于求解作业车间调度问题。仿真实例表明,该算法具有良好的全局收敛性能和快捷的收敛速度,调度效果优于遗传算法、粒子群优化算法和量子粒子群优化算法。     

多目标遗传算法求解认知无线电SUL维持问题

当某个一级用户重新出现时,二级用户必须马上让出属于此一级用户的频谱,此时就存在着如何维持二级用户链接（Secondary Users’Link,SUL）的问题。基于CORVUS系统的“冗余子信道”模型在SUL原有的N个子信道基础上再使用X个冗余子信道进行二级用户之间的通信。只要传输过程中受干扰的子信道个数少于X,接收端就可以从N+X个子信道中恢复出正确信息来,从而解决了SUL维持的问题。但尚未有一种有效的办法以求解最优的N和X。将SUL维持问题建模为一个多目标优化问题,提出了一种基于多目标遗传算法的SUL维持算法SULEA。SULEA能够根据不同的用户服务需求动态地选择适应度函数来求解最优的N和X,Matlab实验证明了SULEA的正确性和有效性。     

Simultaneous optimal selection of design and manufacturing tolerances with alternative manufacturing process selection

Tolerance specification is an important part of mechanical design. Design tolerances strongly influence the functional performance and manufacturing cost of a mechanical product. Tighter tolerances normally produce superior components, better performing mechanical systems and good assemblability with assured exchangeability at the assembly line. However, unnecessarily tight tolerances lead to excessive manufacturing costs for a given application. The balancing of performance and manufacturing cost through identification of optimal design tolerances is a major concern in modern design. Traditionally, design tolerances are specified based on the designer’s experience. Computer-aided (or software-based) tolerance synthesis and alternative manufacturing process selection programs allow a designer to verify the relations between all design tolerances to produce a consistent and feasible design. In this paper, a general new methodology using intelligent algorithms viz., Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) and Multi Objective Particle Swarm Optimization (MOPSO) for simultaneous optimal selection of design and manufacturing tolerances with alternative manufacturing process selection is presented. The problem has a multi-criterion character in which 3 objective functions, 3 constraints and 5 variables are considered. The average fitness factor method and normalized weighted objective functions method are separately used to select the best optimal solution from Pareto optimal fronts. Two multi-objective performance measures namely solution spread measure and ratio of non-dominated individuals are used to evaluate the strength of Pareto optimal fronts. Two more multi-objective performance measures namely optimiser overhead and algorithm effort are used to find the computational effort of NSGA-II and MOPSO algorithms. The Pareto optimal fronts and results obtained from various techniques are compared and analysed.     

均匀设计抽样混合遗传算法求解图的二划分问题

遗传算法(GA)的运行机理及特点是具有定向制导的随机搜索技术,其定向制导的原则是:导向以高适应度模式为祖先的"家族"方向。以此结论为基础,利用均匀设计抽样(UDS)的理论和方法,对遗传算法中的交叉操作进行重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个求解图二划分问题的新遗传算法,称之为基于均匀设计抽样的混合遗传算法。最后将该算法与简单遗传算法和佳点集遗传算法进行比较。通过模拟比较,可以看出新算法不但提高了算法的求解速度和精度,而且避免了常有的早期收敛现象。