改进的群搜索优化算法

标准的群搜索优化算法(GSO)是一种新的群智能优化算法,适用于解决高维函数的优化问题,而且简单高效,易于实现,但在其优化的后期容易陷入局部最优.为进一步提高其收敛速度和精度,对GSO算法进行了改进.保留其"发现者-加入者"模型,针对GSO算法发现者和游荡者搜索的无目的性,引进最大下降方向和杂交策略,发现者按角度搜索的同时也按最大下降方向进行搜索,游荡者通过基因突变策略的方式生成.通过23个基准测试函数对GSO算法和改进的GSO算法进行测试,结果表明改进的GSO算法在收敛速度和收敛精度上优于标准GSO算法.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数-对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

时变情境下的企业应急决策矛盾问题分析与求解

企业应急决策是一个充满变化、矛盾冲突的,涉及多个领域知识的复杂决策过程,能否根据突发事件的发展过程,依照具体的决策情境有效地整合企业可利用的资源条件,化解应急决策过程中的矛盾问题冲突,生成有效的应急决策方案,成为制约应急决策有效性的难点.为此,将可拓学中转换桥方法引入应急决策,研究变化情境下的应急决策矛盾问题分析与求解.针对变化情境下企业应急决策矛盾问题进行形式化基元模型表达,构建了矛盾问题定量描述与求解的转换桥共存度函数和转换桥可拓变换函数,并给出了基于转换桥模型的矛盾问题求解策略.并以某手机制造企业为例,随着突发事件的发展变化,分析企业可利用资源和应急决策过程中的矛盾问题,并进行求解.经验证,所提方法对于分析和解决应急决策过程中不同领域知识之间的对立冲突问题是有效的.     

求解全局优化问题的改进蝙蝠算法[英文]

蝙蝠算法(BA)是一类基于试探技巧的群智能优化算法,该算法已被广泛用于诸多领域问题的求解.本文提出一个改进的蝙蝠算法NIBA.在算法中,为了加强蝙蝠算法的局部和全局搜索能力,提出了三个改进策略.首先,为了改进蝙蝠的局部搜索能力,在当前最优解处给出了一个新的搜索方程.其次,为了改进算法的全局搜索能力,平衡算法的开发能力和探索能力,算法吸收并改进了和声搜索机制.最后,为了进一步提高NIBA算法的搜索能力,在当前最优解处,算法采用了混沌搜索机制.为了验证算法的性能,针对18个标准测试函数进行了数值实验.与其它算法的比较结果显示,NIBA算法具有更好的稳定性,且效率更高.     

基于混合算法的实时订货信息下的车辆调度优化

实时订货信息下的车辆调度是随机性车辆调度中货物需求量、需求点均不确定的情况下的车辆调度.针对该问题,本文构建了配送总成本最小的目标函数,提出了采用混合算法求解的思路.即以局部搜索法求得初始解,采用遗传算法优化初始解,并在送货时间更新后,利用禁忌搜索法求解速度快的特点改进调度方案,得到订货信息不断更新的条件下的车辆调度方案.通过实例分析,本方法既可解决电子商务条件下实时订货的车辆调度问题,也具有求解结果可靠、求解过程快速的特点.     

基于混合单亲遗传算法的车辆运输问题求解

本文运用混合单亲遗传算法(Hybrid Partheno Genetic Algorithm,)求解车辆运输问题.我们用罚函数法将约束优化问题转化为无约束优化问题,HPGA采用序号编码的方式进行运算.生成初始种群时,在拟染色体中插入车辆序号,尽可能生成符合约束的子路径,由子路径拼接成完整的运输路径,降低罚函数的计算量;选择操作中内嵌最优保存策略,保证算法全局收敛;取消双亲交叉操作,每条染色体上独立改变基因产生新的个体,避免发生早熟早收敛现象;提出邻域搜索,使得GA能对某些指定区域进行重点搜索,加快算法在最优解附近的寻优速度;以CVRP作为HPGA的测试模型,采用Christofides和Eilon提出的标准VRP测试算例进行数值实验,和其他算法进行对比分析,验证了HPGA计算量少、收敛速度快和不会产生早熟早收敛现象.     

改进多目标量子粒子群算法的WSN覆盖及能耗均衡

为了使无线传感器网络的覆盖率和能耗达到最优的效果,提出了一种改进的多目标粒子群优化算法,采用量子粒子群优化更新粒子,利用拥挤距离排序策略,并结合适应度函数值优劣特性对多目标矛盾的性能目标选择,同时通过拥挤距离对加速系数自适应调整提高算法搜索能力,得到了逼近真实前沿的Pareto解集,具有更快的收敛速度和更强的寻优能力.通过对比实验结果表明:提出的算法在解决WSN的多目标优化问题时,能够避免算法陷入局部最优解,更好地平衡网络覆盖和动态通信能耗,使整个网络的综合指数达到了6.249,均明显优于其他三种算法.     

秘书问题研究综述：何时停止搜索信息?

秘书问题是一类序贯观察与选择问题,描述了一种动态的信息搜索与决策过程,其问题实质是决定何时停止观察选项、而不是哪一个选项被选择.已有研究成果从解决该问题的策略方法角度,可以分为最优解策略与启发式策略,二者的差异主要体现在理论依据与研究方法上.最优解策略基于决策者完全理性假设,运用数学模型论证了解决该问题的最优决策行为。但许多实证研究发现,人们往往并没有遵循最优决策行为。相比较最优解策略而言,人们通常停止搜索信息太早或者说搜索量太少。这种基于决策者有限理性假设的描述性研究,在解释人们最优选择行为偏离的基础上,提出了解决秘书问题的一些启发式策略.最后,本文通过对已有研究成果的梳理与分析,提出了进一步研究的问题与方向。     

含有不可靠节点的无圈序贯网络可靠性分析

首次对含有不可靠节点的无圈序贯网络(Acyclic consecutively connected networks,ACCN)的可靠性进行分析.并首次提出n中取[k_1,k_2]节点的概念:当节点接收到的信号数量不小于k_1且不大于k_2时节点正常,否则失效.针对含有不可靠节点的.ACCN的性质对一般生成函数进行改进,建立节点的改进一般生成函数.随后根据改进一般生成函数的特点对递归过程进行简化.最后给出一个含有不完全可靠节点的网络的算例,利用改进一般生成函数和简化的递归过程对网络的可靠性进行评价,证明改进后的方法解决了含有不可靠节点的ACCN可靠性评价问题并有效的简化了计算过程.     

Variable and large neighborhood search to solve the multiobjective set covering problem

In this paper, we study the multiobjective version of the set covering problem. To our knowledge, this problem has only been addressed in two papers before, and with two objectives and heuristic methods. We propose a new heuristic, based on the two-phase Pareto local search, with the aim of generating a good approximation of the Pareto efficient solutions. In the first phase of this method, the supported efficient solutions or a good approximation of these solutions is generated. Then, a neighborhood embedded in the Pareto local search is applied to generate non-supported efficient solutions. In order to get high quality results, two elaborate local search techniques are considered: a large neighborhood search and a variable neighborhood search. We intensively study the parameters of these two techniques. We compare our results with state-of-the-art results and we show that with our method, better results are obtained for different indicators.     

A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty

This paper presents a metaheuristic solution approach based on Tabu search for the open-pit mine production scheduling problem with metal uncertainty. To search the feasible domain more extensively, two different diversification strategies are used to generate several initial solutions to be optimized by the Tabu search procedure. The first diversification strategy exploits a long-term memory of the search history. The second one relies on the variable neighborhood search method. Numerical results on realistic large-scale instances are provided to indicate the efficiency of the solution approach to produce very good solutions in relatively short computational times.     

Metaheuristic methods based on Tabu search for assigning judges to competitions

Two metaheuristic methods based on Tabu search are introduced to assign judges to individual competitions in a tournament. The complexity of the mathematical formulation accounting for the assignment rules, leads us to use such an approach. The first metaheuristic includes two different Tabu searches that are combined with a diversification strategy. The second metaheuristic is applied to a penalized version of the original model formulated as an assignment problem. This metaheuristic is also based on a Tabu search procedure including a diversification strategy driven by the constraints violated. Numerical results are provided to indicate the efficiency of the methods to generate very good solutions.     

Annealing-tabu PAES: a multi-objective hybrid meta-heuristic

Most real-life optimization problems require taking into account not one, but multiple objectives simultaneously. In most cases these objectives are in conflict, i.e. the improvement of some objectives implies the deterioration of others. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined, but rather a set of solutions. In the last decade most papers dealing with multi-objective optimization use the concept of Pareto-optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of non-dominated solutions as an approximation to the true Pareto-optimal front. However, this front is unknown for problems with large and highly complex search spaces, which is why meta-heuristic methods have become important tools for solving this kind of problem. Hybridization in the multi-objective context is nowadays an open research area. This article presents a novel extension of the well-known Pareto archived evolution strategy (PAES) which combines simulated annealing and tabu search. Experiments on several mathematical problems show that this hybridization allows an improvement in the quality of the non-dominated solutions in comparison with PAES, and also with its extension M-PAES.     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

可拓策略生成方法与技术研究

知识激活乃至策略生成问题目前仍然是属于探索性阶段.研究了知识生成和智能激发的可拓方法,其核心是利用可拓变换与拓展推理解决矛盾问题,它为技术实现策略生成探索出一条可行之路.     

An accelerated covering relaxation algorithm for solving 0–1 positive polynomial programs

The purpose of this note is to present an accelerated algorithm for solving 0–1 positive polynomial (PP) problems. Like our covering relaxation algorithm (Management Science 1979), the accelerated algorithm is a cutting plane method, which uses the linear set covering problem as a relaxation for PP. However, a unique and novel feature of the accelerated algorithm is that it attempts to generate cutting planes from heuristic solutions to the set covering problem whenever possible. Computational results reveal that this strategy of generating cutting planes has led to a significant reduction in the computational time required to solve a PP problem.This research was partially supported by National Sciences and Engineering Research Council Canada Grants 67-4181 and 67-3998, Office of Naval Research Contract N00014-76-C-0418, and National Science Foundation Grant ECS80-22027.     

The travelling salesperson problem with hotel selection

In this paper, we present the travelling salesperson problem with hotel selection (TSPHS), an extension of the TSP with a number of interesting applications. We present a mathematical formulation, explain the difference with related optimization problems and indicate what makes this problem inherently more difficult. We develop a simple but efficient heuristic that uses two constructive initialization procedures and an improvement procedure consisting of several neighbourhood search operators designed specifically for this problem, as well as some typical neighbourhoods from the literature. We generate several benchmark instances of varying sizes and compare the performance of our heuristic with CPLEX (10.0). We also generate some problems with known optimal solutions and use these to further demonstrate that our heuristic achieves good results in very limited computation times.     

提高软件Agent策略生成的语义互操作能力

软件Agent遇到语义二义性时无法正确地为用户解决矛盾问题.利用本体支持语义互操作的特点,在软件Agent策略生成机制中引入复合元本体,加入Agent智能引导的人机交互方法,实现了具有语义歧义消除能力的可拓策略生成系统.当用户输入的问题信息语义模糊时,Agent根据本体中的知识与用户交互,逐步理解用户的信息语义,直到能为用户生成解决矛盾问题的策略.以旅游与购物问题为例进行了实验,结果表明了软件Agent策略生成的语义互操作能力得到了提高.     

A metaheuristic for the vehicle-routeing problem with soft time windows

This paper develops a metaheuristic for the vehicle-routeing and scheduling problem with soft time window constraints. A tabu search solution method is developed, which utilizes a mixed neighbourhood structure and an advanced recovery procedure to generate high-quality solutions. Computational results on test problems from the literature are reported. The metaheuristic achieves solutions that compare favourably with previously reported results.