多元优化算法及其收敛性分析

提出了一种搜索个体分工明确、协同合作的群智能优化算法,并从理论上证明了其收敛性. 由于搜索个体(搜索元)具有分工不同的多元化特点,所以我们称该算法为多元优化算法(Multivariant optimization algorithm, MOA).多元优化算法中, 全局搜索元和局部搜索元基于数据表高效的记录和分享信息以协同合作对解空间进行搜索. 在一次迭代中,全局搜索元搜索整个解空间以寻找潜在解区域,然后具有不同种群大小的局部搜索元组对潜力不同的历史潜在解区域以及新发现的潜在解区域进行不同粒度的搜索. 搜索元找到的较优解按照一定的规则保存在由队列和堆栈组成的结构体中以实现历史信息的高效记忆和共享. 结构体中保存的候选解在迭代过程中不断更新逐渐接近最优解,最终找到优化问题的多个全局最优解以及局部次优解.基于马尔科夫过程的理论分析表明:多元优化算法以概率1 收敛于全局最优解.为了评估多元优化算法的收敛性,本文利用多元优化算法以及其他五个常用的优化算法对十三个二维及十维标准测试函数进行了寻优测试. 实验结果表明,多元优化算法在收敛成功率和收敛精度方面优于其他参与比较的算法.     

分散搜索算法求解多目标优化问题

最近涌现了各种进化方法来解决多目标优化问题,分散搜索也是一种可以解决多目标问题的算法。该算法的结构引用进化算法的杂交和变异算子来增强它的性能,但该算法与其他进化算法的不同在于一系列操作策略不再基于随机性原理,而是运用“分散-收敛集聚”的迭代机制。论文在多目标优化问题区域讨论分散搜索算法,寻找多目标的非支配集或Pareto最优解。实验表明,分散搜索算法具有很好的收敛性和分布性。     

一种动态窗口下改进的机器人路径规划

提出了蚁群路径规划算法中一种动态候选解窗口的方法。该方法首先在固定均匀分布候选解的窗口上划分成若干分块,接着将负责路径规划的主蚁群的候选决策点看作一系列具有候选解属性的蚂蚁,再用该蚁群算法根据每分块上所有候选解上游连接边上的信息素及其启发信息以一定概率动态分布候选决策点,从而细化候选解,最终使蚁群能搜索到一条更好的路径解。仿真实验和对比的结果表明,动态候选解窗口方法比固定均匀分布候选解的方法可获得更优的性能。     

A review of metrics on permutations for search landscape analysis

Search landscape analysis has become a central tool for analysing the dependency of the performance of stochastic local search algorithms on structural aspects of the spaces being searched. Central to search landscape analysis is the notion of distance between candidate solutions. This distance depends on some underlying basic operator and it is defined as the minimum number of operations that need to be applied to one candidate solution for transforming it into another one. For operations on candidate solutions that are represented by permutations, in almost all researches on search landscape analysis surrogate distance measures are applied, although efficient algorithms exist in many cases for computing the exact distances. This discrepancy is probably due to the fact that these efficient algorithms are not very widely known. In this article, we review algorithms for computing distances on permutations for the most widely applied operators and present simulation results that compare the exact distances to commonly used approximations.     

A production base-stock policy for recycling supply chain management in the presence of uncertainty

This study focuses on solving master planning problems for a recycling supply chain with uncertain supply and demand. A recycling supply chain network includes collectors, disassemblers, remanufacturers, and redistributors working from the collection of returned goods to the distribution of recovered products to the market. The objective of this study is to maximize the total profit of the entire recycling supply chain. Considering the stochastic property of the recycling supply chain, this study institutes stocking and processing policies for each member of the recycling supply chain to better respond to unknown future demand. We propose a heuristic algorithm called stochastic recycling process planning algorithm (SRPPA) to address master planning problems in the recycling supply chain and its supply and demand uncertainties. The main SRPPA process consists of three phases. In the leader determination phase, SRPPA identifies the most important node as the leader of the recycling supply chain. In the candidate policy set generation phase, SRPPA defines the search range for the inventory policy and forms the candidate policy sets based on the characteristics of the leader. In the best policy set selection phase, SRPPA constructs the simulation process for each inventory policy candidate to identify the best policy set. A scenario analysis is then presented to show the effectiveness and efficiency of SRPPA.     

A hybrid estimation of distribution algorithm for simulation-based scheduling in a stochastic permutation flowshop

The permutation flowshop scheduling problem (PFSP) is NP-complete and tends to be more complicated when considering stochastic uncertainties in the real-world manufacturing environments. In this paper, a two-stage simulation-based hybrid estimation of distribution algorithm (TSSB-HEDA) is presented to schedule the permutation flowshop under stochastic processing times. To deal with processing time uncertainty, TSSB-HEDA evaluates candidate solutions using a novel two-stage simulation model (TSSM). This model first adopts the regression-based meta-modelling technique to determine a number of promising candidate solutions with less computation cost, and then uses a more accurate but time-consuming simulator to evaluate the performance of these selected ones. In addition, to avoid getting trapped into premature convergence, TSSB-HEDA employs both the probabilistic model of EDA and genetic operators of genetic algorithm (GA) to generate the offspring individuals. Enlightened by the weight training process of neural networks, a self-adaptive learning mechanism (SALM) is employed to dynamically adjust the ratio of offspring individuals generated by the probabilistic model. Computational experiments on Taillard’s benchmarks show that TSSB-HEDA is competitive in terms of both solution quality and computational performance.     

一种混沌贝叶斯优化算法

为了减少贝叶斯优化算法的计算量,该文提出了一种混沌贝叶斯优化算法。用混沌随机序列产生贝叶斯优化算法的初始群体,利用混沌随机性、遍历性和对初始条件的敏感性的特点,提供给贝叶斯网络变量空间丰富的信息,有利于建立接近最优的贝叶斯网络。为增加群体的多样性同时减少贝叶斯网络的建立次数,采用混沌搜索方法对贝叶斯网络产生的新解进行变异寻优,以此为基础再建立贝叶斯网络。实验结果表明,与贝叶斯优化算法相比,混沌贝叶斯优化算法能有效减少计算量。     

一种新的启发式分类器选择方法

分类器选择是一种设计多分类器系统的有效方法,从给定候选分类器集中挑选出一个子集,使得该子集集成性能最佳。现有的分类器选择方法大多采用基于集成精度的随机搜索方法,但巨大的搜索复杂度限制了它们在更大系统中的应用。该文提出一种新的选择标准——IWCECR及一种基于IWCECR的启发式搜索算法,在手写体数字识别的实验中,从20个候选分类器中挑选子集,结果表明,该方法具有较高的搜索效率,在子集集成性能方面仅次于穷举法。     

车辆路径问题的双重进化蜂群算法求解研究

针对传统人工蜂群算法局部搜索的低效性,提出了双重进化人工蜂群算法。在需要两点进行操作的搜索过程中,采用一点随机选取,另一点通过遍历可行解,以其中最优解确定位置的半随机式搜索策略。用该策略改进插入点算子和逆转序列算子,分别在两对以及三对城市间距离之和的解空间维度上交叉搜索,并应用到局部搜索中构成双重进化过程,提高了搜索效率和适应值引导性。实验结果表明,该算法较已有方法提高了收敛速度,优化了目标解,并可通过合理设置终止阈值提高时效性。     

基于改进遗传算法的资源优化配置研究

当前在解决资源优化配置问题时往往使用贪婪算法、遗传算法等.但贪婪算法只能选择一个最优度量标准,所以只能获得度量意义下的最优解而不是该问题的最优解,而如果直接使用遗传算法又存在搜索空间过大、耗时过长的问题.提出了一种新的算法.先基于贪婪算法获得问题的初始解空间,然后对初始解空间进行冲突检测与消解,最后运用改进的遗传算法进行优化获得最优方案.测试算例表明大大缩小了遗传算法的搜索空间,在保证获得最优解的条件下加快了收敛速度并有效防止了种群的退化.提出的算法在突发事务的处理方面具有一定的意义.     

随机扩散算法求解二次背包问题

针对二次背包问题,提出一种新的基于群体智能的随机扩散算法．算法采用一对一的通信机制;利用部分函数估计评价候选解;利用量子机制构造个体;采用1-OPT异或操作提高搜索性能．通过数值实验并与微粒群算法、蚁群算法作比较,结果表明算法具有较好的优化性能．     

Application of graph search and genetic algorithms for the single machine scheduling problem with sequence-dependent setup times and quadratic penalty function of completion times

In this paper, we consider the single machine scheduling problem with quadratic penalties and sequence-dependent (QPSD) setup times. QPSD is known to be NP-Hard. Only a few exact approaches, and to the best of our knowledge, no approximate approaches, have been reported in the literature so far. This paper discusses exact and approximate approaches for solving the problem, and presents empirical findings. We make use of a graph search algorithm, Memory-Based Depth-First Branch-and-Bound (MDFBB), and present an algorithm, QPSD_MDFBB that can optimally solve QPSD, and advances the state of the art for finding exact solutions. For finding approximate solutions to large problem instances, we make use of the idea of greedy stochastic search, and present a greedy stochastic algorithm, QPSD_GSA that provides moderately good solutions very rapidly even for large problems. The major contribution of the current paper is to apply QPSD_GSA to generate a subset of the starting solutions for a new genetic algorithm, QPSD_GEN, which is shown to provide near-optimal solutions very quickly. Owing to its polynomial running time, QPSD_GEN can be used for much larger instances than QPSD_MDFBB can handle. Experimental results have been provided to demonstrate the performances of these algorithms.     

基于混合算法的带时间窗的车辆路径问题求解

建立了有时间窗车辆路径问题的数学模型，针对遗传算法在局部搜索能力方面的不足，提出将模拟退火算法与遗传算法相结合，从而构造了有时间窗车辆路径问题的混合遗传算法，并进行了实验计算。结果表明，用混合遗传算法求解该优化问题，可以在一定程度上克服遗传算法在局部搜索能力方面的不足和模拟退火算法在全局搜索能力方面的不足，从而得到了质量较高的解。     

Parallel chaos optimization algorithm with migration and merging operation

Chaos optimization algorithm (COA) utilizes the chaotic maps to generate the pseudo-random sequences mapped as the decision variables for global optimization applications. A kind of parallel chaos optimization algorithm (PCOA) has been proposed in our former studies to improve COA. The salient feature of PCOA lies in its pseudo-parallel mechanism. However, all individuals in the PCOA search independently without utilizing the fitness and diversity information of the population. In view of the limitation of PCOA, a novel PCOA with migration and merging operation (denoted as MMO-PCOA) is proposed in this paper. Specifically, parallel individuals are randomly selected to be conducted migration and merging operation with the so far parallel solutions. Both migration and merging operation exchange information within population and produce new candidate individuals, which are different from those generated by stochastic chaotic sequences. Consequently, a good balance between exploration and exploitation can be achieved in the MMO-PCOA. The impacts of different one-dimensional maps and parallel numbers on the MMO-PCOA are also discussed. Benchmark functions and parameter identification problems are used to test the performance of the MMO-PCOA. Simulation results, compared with other optimization algorithms, show the superiority of the proposed MMO-PCOA algorithm.     

Evolving recurrent perceptrons for time-series modeling

Evolutionary programming, a systematic multi-agent stochastic search technique, is used to generate recurrent perceptrons (nonlinear IIR filters). A hybrid optimization scheme is proposed that embeds a single-agent stochastic search technique, the method of Solis and Wets, into the evolutionary programming paradigm. The proposed hybrid optimization approach is further augmented by "blending" randomly selected parent vectors to create additional offspring. The first part of this work investigates the performance of the suggested hybrid stochastic search method. After demonstration on the Bohachevsky and Rosenbrock response surfaces, the hybrid stochastic optimization approach is applied in determining both the model order and the coefficients of recurrent perceptron time-series models. An information criterion is used to evaluate each recurrent perceptron structure as a candidate solution. It is speculated that the stochastic training method implemented in this study for training recurrent perceptrons can be used to train perceptron networks that have radically recurrent architectures.     

搜索算法的逻辑分析*

搜索算法的初始空间、搜索策略、搜索过程可以用一阶语言描述,搜索算法的逻辑性质由初始状态空间确定.这意味着描述搜索过程的逻辑具有紧致性,初始状态的初等类具有有限封闭性.     

Electromagnetism-like algorithms for optimized tool path planning in 5-axis flank machining

Optimization of tool path planning using metaheuristic algorithms such as ant colony systems (ACS) and particle swarm optimization (PSO) provides a feasible approach to reduce geometrical machining errors in 5-axis flank machining of ruled surfaces. The optimal solutions of these algorithms exhibit an unsatisfactory quality in a high-dimensional search space. In this study, various algorithms derived from the electromagnetism-like mechanism (EM) were applied. The test results of representative surfaces showed that all EM-based methods yield more effective optimal solutions than does PSO, despite a longer search time. A new EM-MSS (electromagnetism-like mechanism with move solution screening) algorithm produces the most favorable results by ensuring the continuous improvement of new searches. Incorporating an SPSA (simultaneous perturbation stochastic approximation) technique further improves the search results with effective initial solutions. This work enhances the practical values of tool path planning by providing a satisfactory machining quality.     

A List Based Threshold Accepting Algorithm for the Capacitated Vehicle Routing Problem

The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the Capacitated Vehicle Routing Problem (CVRP), termed as the List Based Threshold Accepting (LBTA) algorithm. The main advantage of this algorithm over the majority of other meta-heuristics is that it produces quite satisfactory solutions in reasonable amount of time by tuning only one parameter of the algorithm. This property makes this algorithm a reliable and a practical tool for every decision support system designed for solving real life vehicle routing problems.     

Towards efficiently searching triple product property triples: Deterministic and randomized algorithms

The key objects in the group-theoretic approach to matrix multiplication are subsets of a group satisfying the so-called triple product property (TPP). In this paper, we focus on the problem of efficiently finding the triple product property triples. We deduce and present some new characteristics of the tripleproduct property. Using these new characteristics, we firstly propose an efficient deterministic algorithm in which a screening process based on historical information is designed to reduce the search space. In contrast to some of the recent heuristic search methods, the proposed deterministic algorithm can search all kinds of TPP triples in a highly efficient way with the help of a novel representation for subsets and a Moving 1 principle. In addition, we also propose an efficient randomized algorithm for finding TPP triples, which adopts a greedy randomized strategy to randomly generate possible TPP candidates. Experimental results demonstrate that our proposed deterministic algorithm can achieve a huge speed-up in terms of running time compared with the existing deterministic algorithm, and the proposed randomized algorithm outperforms other existing approaches for finding TPP triples.     

Representation and structural difficulty in genetic programming

Standard tree-based genetic programming suffers from a structural difficulty problem in that it is unable to search effectively for solutions requiring very full or very narrow trees. This deficiency has been variously explained as a consequence of restrictions imposed by the tree structure or as a result of the numerical distribution of tree shapes. We show that by using a different tree-based representation and local (insertion and deletion) structural modification operators, that this problem can be almost eliminated even with trivial (stochastic hill-climbing) search methods, thus eliminating the above explanations. We argue, instead, that structural difficulty is a consequence of the large step size of the operators in standard genetic programming, which is itself a consequence of the fixed-arity property embodied in its representation.