基于文化基因算法的开放车间调度问题研究

针对开放车间调度问题,运用了文化基因算法进行优化求解。在文化基因算法的框架中,既有种群中的全局搜索,又包含针对问题自身特点的局部搜索,为解决开放车间调度问题提供了一种新的算法。按照文化基因算法的思想和特点,将爬山法作为局部搜索策略加入到全局搜索策略所用到的遗传算法中,通过对开放车间调度问题的邻域结构进行研究,加入爬山搜索法进行优化求解。基于40个标准算例,通过与下界值的比较,验证了所提算法在解决具有较大搜索空间的调度问题时,其拥有更出色的算法性能。     

Cross-docking truck scheduling with product unloading/loading constraints based on an improved particle swarm optimisation algorithm

Cross-docking is a very useful logistics technique that can substantially reduce distribution costs and improve customer satisfaction. A key problem in its success is truck scheduling, namely, decision on assignment and docking sequence of inbound/outbound trucks to receiving/shipping dock doors. This paper focuses on the problem with the requirement of unloading/loading products in a given order, which is very common in many industries, but is less concerned by existing researches. An integer programming model is established to minimise the makespan. An improved particle swarm optimisation (ωc-PSO) algorithm is proposed for solving it. In the algorithm, a cosine decreasing strategy of inertia weight is designed to dynamically balance global and local search. A repair strategy is put forward for continuous search in the feasible solution space and a crossover strategy is presented to prevent the algorithm from falling into local optimum. After algorithm parameters are tuned using Taguchi method, computational experiments are conducted on different problem scales to evaluate ωc-PSO against genetic algorithm, basic PSO and GLNPSO. The results show that ωc-PSO outperforms other three algorithms, especially when the number of dock doors, trucks and product types is great. Statistical tests show that the performance difference is statistically significant.     

Two-dimensional phase unwrapping using a hybrid genetic algorithm

A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.     

基于改进免疫遗传优化蚁群算法的移动机器人路径寻优研究

针对移动机器人路径规划中使用蚁群算法(ACO)易陷入局部最优和收敛速度慢的问题,提出了一种适用于机器人静态路径寻优的改进免疫遗传优化蚁群算法(IMGAC)。该算法可以根据实际情况自动调整变异概率和变异方式,以及自动调节个体免疫位的长度,将通过改进的变异算子和免疫算子嵌入蚁群算法来提高全局寻优能力与收敛速度。仿真及实验表明:相比于经典ACO算法以及最大最小蚂蚁系统,IMGAC算法收敛速度更快,全局寻优能力更强。利用该算法寻找移动机器人最优路径,提高了静态路径寻优的效果和效率。     

Production scheduling optimization algorithm for the hot rolling processes

The hot rolling production scheduling problem is an extremely difficult and time-consuming process, so it is quite difficult to achieve an optimal solution with traditional optimization methods owing to the high computational complexity. To ensure the feasibility of solutions and improve the efficiency of the scheduling, this paper proposes a vehicle routing problem (VRP) to model the problem and develops an easily implemented hybrid approach (QPSO-SA) to solve the problem. In the hybrid approach, quantum particle swarm optimization (QPSO) combines local search and global search to search the optimal results and simulated annealing (SA) employs certain probability to avoid getting into a local optimum. The computational results from actual production data have shown that the proposed model and algorithm are feasible and effective for the hot rolling scheduling problem.     

图的度量维数问题的0-1蚁群条件着色分辨算法研究

图的度量维数问题（MDP）是一类在机器导航、声呐系统布置、化学、数据分类等领域有重要应用的组合优化问题．针对该问题,本文通过引入图的分辨表存储结构,建立了非线性求解模型;同时,通过改进现有蚁群算法的参数设计,利用全局搜索和局部搜索相结合的策略,建立了求解模型的改进型蚁群算法．数值对比分析验证了算法的有效性：全局搜索和局部搜索的结合较大程度的改进了算法求解质量;在规则图上提高算法求解质量具有一定挑战;与遗传算法计算结果相比较,本文提出的算法不仅在求解质量方面有所提升,而且在最坏的情况下能为图提供极小分辨集. 最后,本文探索了部分算法参数对算法求解质量的影响,并给出了进一步研究课题．     

遗传禁忌搜索算法在混流装配线排序中的应用

针对混流装配线排序问题，提出了一种混合遗传禁忌搜索算法，在每一代遗传演化之后，按一定比例随机选择部分解进行禁总搜索，以提高算法的全局搜索能力和收敛性。通过一个混流装配线排序实验，分别利用遗传算法和遗传禁忌搜索算法进行求解，结果表明遗传禁忌搜索算法具有更好的全局搜索能力和收敛性能。     

基于速度交流的共生多种群粒子群算法

为了提高粒子群算法的求解精度,改善算法的搜索性能,提出一种基于速度交流的共生多种群粒子群算法(SMPSO)。该算法采用速度交流机制划分整个从种群为多个子种群,负责解空间的全局搜索,将获得的最优信息分享给主种群;主种群综合从种群与自身最优经验,负责局部深度优化,获得最优信息反馈给从种群,从而建立主从群间的共生关系,实现解空间的充分搜索。迭代后期,在主种群中引入自适应变异策略,提高算法跳出局部最优的能力。将提出的SMPSO算法应用于基准测试函数中,与其它改进的PSO算法进行比较。实验结果表明,SMPSO算法在求解精度、搜索能力、稳定性等方面均有较大的提高。     

Heterogeneous Selection Genetic Algorithms For Traveling Salesman Problems

This paper proposes a genetic algorithm, called the heterogeneous selection genetic algorithm (HSGA), integrating local and global strategies via family competition and edge similarity, for the traveling salesman problem (TSP). Local strategies include neighbor-join mutation and family competition, and global strategies consist of heterogeneous pairing selection and edge assembly crossover. Based on the mechanisms of preserving and adding edges, the search behaviors of neighbor-join mutation and edge assembly crossover are studied. The proposed method has been implemented and applied to 17 well-lmown TSPs whose numbers of cities range from 101 to 13,509. Experimental results indicate that this approach, although somewhat slower, performs very robustly and is very competitive with other approaches in the best surveys. This approach is able to find the optimum, and the average solution quality is within 0.00048 above the optima of each test problem.     

A genetic algorithm approach to single and multiobjective structural optimization with discrete–continuous variables

A search procedure with a philosophical basis in molecular biology is adapted for solving single and multiobjective structural optimization problems. This procedure, known as a genetic algorithm (GA). utilizes a blending of the principles of natural genetics and natural selection. A lack of dependence on the gradient information makes GAs less susceptible to pitfalls of convergence to a local optimum. To model the multiple objective functions in the problem formulation, a co-operative game theoretic approach is proposed. Examples dealing with single and multiobjective geometrical design of structures with discrete–continuous design variables, and using artificial genetic search are presented. Simulation results indicate that GAs converge to optimum solutions by searching only a small fraction of the solution space. The optimum solutions obtained using GAs compare favourably with optimum solutions obtained using gradient-based search techniques. The results indicate that the efficiency and power of GAs can be effectively utilized to solve a broad spectrum of design optimization problems with discrete and continuous variables with similar efficiency.     

A biogeography-based optimization for optimum discrete design of skeletal structures

This article presents a modified biogeography-based optimization (MBBO) algorithm for optimum design of skeletal structures with discrete variables. The main idea of the biogeography-based optimization (BBO) algorithm is based on the science of biogeography, in which each habitat is a possible solution for the optimization problem in the search space. This algorithm consists of two main operators: migration and mutation. The migration operator helps the habitats to exploit the search space, while the mutation operator guides habitats to escape from the local optimum. To enhance the performance of the standard algorithm, some modifications are made and an MBBO algorithm is presented. The performance of the MBBO algorithm is evaluated by optimizing five benchmark design examples, and the obtained results are compared with other methods in the literature. The numerical results demonstrate that the MBBO algorithm is able to show very competitive results and has merits in finding optimum designs.     

OPTIMAL STRUCTURAL DESIGN BY ANT COLONY OPTIMIZATION

Ant colony optimization (ACO) is a relatively new heuristic combinatorial optimization algorithm in which the search process is a stochastic procedure that incorporates positive feedback of accumulated information. The positive feedback (;i.e., autocatalysis) facility is a feature of ACO which gives an emergent search procedure such that the (common) problem of algorithm termination at local optima may be avoided and search for a global optimum is possible.

The ACO algorithm is motivated by analogy with natural phenomena, in particular, the ability of a colony of ants to ‘optimize’ their collective endeavours. In this paper the biological background for ACO is explained and its computational implementation is presented in a structural design context. The particular implementation of ACO makes use of a tabu search (TS) local improvement phase to give a computationally enhanced algorithm (ACOTS).

In this paper ACOTS is applied to the optimal structural design, in terms of weight minimization, of a 25-bar space truss. The design variables are the cross-sectional areas of the bars, which take discrete values. Numerical investigation of the 25-bar space truss gave the best (i.e., lowest to-date) minimum weight value. This example provides evidence that ACOTS is a useful and technically viable optimization technique for discrete-variable optimal structural design.     

A variant space search method and its application to the optimization design of compressor profiles

Optimization methods have been widely used in practical engineering, with search efficiency and global search ability being the main evaluation criteria. In this article, the Bezier curve equivalent recursion is used in a genetic algorithm (GA) to realize the variant space search to improve the search efficiency and global search ability. The parameters related to this method are investigated by an optimization test of the simple curve approximation, which is then used for optimization designs of supersonic and transonic profiles. The results show that the GA can be improved if the variant space search method is added.     

An efficient and practical approach to obtain a better optimum solution for structural optimization

For many structural optimization problems, it is hard or even impossible to find the global optimum solution owing to unaffordable computational cost. An alternative and practical way of thinking is thus proposed in this research to obtain an optimum design which may not be global but is better than most local optimum solutions that can be found by gradient-based search methods. The way to reach this goal is to find a smaller search space for gradient-based search methods. It is found in this research that data mining can accomplish this goal easily. The activities of classification, association and clustering in data mining are employed to reduce the original design space. For unconstrained optimization problems, the data mining activities are used to find a smaller search region which contains the global or better local solutions. For constrained optimization problems, it is used to find the feasible region or the feasible region with better objective values. Numerical examples show that the optimum solutions found in the reduced design space by sequential quadratic programming (SQP) are indeed much better than those found by SQP in the original design space. The optimum solutions found in a reduced space by SQP sometimes are even better than the solution found using a hybrid global search method with approximate structural analyses.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

求解约束优化问题的改进布谷鸟搜索算法

为了提高约束优化问题的求解精度和收敛速度,提出求解约束优化问题的改进布谷鸟搜索算法。首先分析了基本布谷鸟搜索算法全局搜索和局部搜索过程中的不足,对其中全局搜索和局部搜索迭代公式进行重新定义,然后以一定概率在最优解附近进行搜索。对12个标准约束优化问题和4个工程约束优化问题进行测试并与多种算法进行对比,实验结果和统计分析表明所提算法在求解约束优化问题上具有较强的优越性。     

改进智能水滴算法在车辆调度问题中的应用

目的克服标准智能水滴(IWD)算法泥土含量更新对象较为单一的缺点,提高其求解车辆调度问题的全局搜索能力。方法在IWD算法基础上,设计一种改进智能水滴(IIWD)算法用于车辆调度问题的求解。引入次优解集合的概念,每次迭代结束后同时更新最优解集合和次优解集合中的泥土含量;设计浑沌扰动机制,对陷入局部最优解的智能水滴进行浑沌扰动;根据车辆调度问题的特点,提出求解车辆调度问题的IIWD算法。结果得到含有8条子路径,总行驶距离为842.60 km的最优调度方案,相对于标准IWD算法(941.35 km)和遗传算法(860.76 km)的求解结果分别缩短了98.75和18.16km。结论与遗传算法和标准IWD算法相比较,IIWD算法在求解车辆调度问题时收敛速度更快,全局优化能力更高。     

基于分布式猴群算法的传感器优化布置方法研究

建立了针对具有较多自由度的大型结构传感器优化布置的分布式猴群算法。通过引入双重编码的方式, 克服了原猴群算法只能解决连续变量的缺陷;针对单个猴群全局搜索能力较弱的问题, 提出了一种将初始化产生的大量猴子个体按照指定的方式分配到多个猴群进行同步并行搜索的方法;考虑原猴群算法能够跳出局部最优的特点以及和声算法较强的局部搜索能力, 提出将每个猴群得到的初步最优解作为初始和声记忆库, 采用基本和声算法进行二次搜索的方法, 来获取传感器的最终布设方案。文末以大连国贸大厦为例, 进行了参数敏感性分析以及传感器优化布置方案的选择, 结果表明分布式猴群算法具有较强的全局寻优能力, 非常适用于具有较多自由度的大型结构传感器优化布置。     

基于IHHO算法的光伏电池工程模型的参数辨识

针对HHO算法存在搜索过程调整不够灵活,不能针对性地进行阶段性搜索,有时会陷入局部最优使算法搜索精度相对较差等问题,提出了一种基于改进哈里斯鹰优化(IHHO)算法的参数辨识方法。对HHO算法进行了两项改进:引入柔性递减策略,在迭代初期扩大全局搜索范围,在迭代后期延长局部搜索时间,从而加强了初期的全局搜索能力和后期的局部搜索能力;引入黄金正弦法,不但增加了种群的多样性,减少算法陷入局部最优的可能性,并且缩小了搜索空间,提高了寻优效率。应用于光伏电池工程模型的参数辨识中,IHHO算法比其他算法得到的辨识结果更为精确,辨识结果与实测数据拟合度更高,IHHO算法能够在不同环境下对光伏电池的工程模型进行准确的参数辨识。     

Multiple colony ant algorithm for job-shop scheduling problem

Ant colony optimization (ACO) is a metaheuristic that takes inspiration from the foraging behaviour of a real ant colony to solve the optimization problem. This paper presents a multiple colony ant algorithm to solve the Job-shop Scheduling Problem with the objective that minimizes the makespan. In a multiple colony ant algorithm, ants cooperate to find good solutions by exchanging information among colonies which are stored in a master pheromone matrix that serves the role of global memory. The exploration of the search space in each colony is guided by different heuristic information. Several specific features are introduced in the algorithm in order to improve the efficiency of the search. Among others is the local search method by which the ant can fine-tune their neighbourhood solutions. The proposed algorithm is tested over set of benchmark problems and the computational results demonstrate that the multiple colony ant algorithm performs well on the benchmark problems.