一种基于免疫原理求解TSP问题的模型

基于人工免疫原理，建立了一个基于免疫机制求解TSP问题的数学模型。在该模型中，定义了TSP问题中的抗原和抗体，描述了记忆细胞动态进化过程，并借鉴遗传算法中基因变异思想，提出了优势基因进化的GFE算法，结合生物免疫系统抗体浓度稳定原理，在克隆选择过程中实现了抗体集合的进化计算，快速有效地求解出问题的全局近似最优解。实验结果表明该算法对解决组合优化问题不仅可行，而且有较快的收敛速度和较强的全局搜索能力。     

求解TSP问题的人工鱼群算法

人工鱼群算法在函数优化问题中取得了较好的应用,但在组合优化问题中的应用相对较少。因此,文中用人工鱼群算法来求解TSP问题,并与标准粒子群算法和基本遗传算法进行了比较分析。通过仿真实验对公认的TSP测试数据中算例Oliver30进行测试并与目前已知最优解进行了对比,结果表明,人工鱼群算法解决TSP问题时可以收敛到已知最优解,并且解的质量要优于标准粒子群算法和基本遗传算法。     

求解TSP问题的人工鱼群算法

人工鱼群算法在函数优化问题中取得了较好的应用,但在组合优化问题中的应用相对较少。因此,文中用人工鱼群算法来求解TSP问题,并与标准粒子群算法和基本遗传算法进行了比较分析。通过仿真实验对公认的TSP测试数据中算例Oliver30进行测试并与目前已知最优解进行了对比,结果表明,人工鱼群算法解决TSP问题时可以收敛到已知最优解,并且解的质量要优于标准粒子群算法和基本遗传算法。     

用改进的EAX算法求解TSP问题的研究

TSP问题是一个经典的NP问题,它要求解一条经过连通网络的所有顶点当且仅当一次且距离最短的回路,即距离最短的Hamilton回路问题。本文在研究利用遗传算法求解TSP问题的基础上,重点论述EAX算法并对E-set选择策略加以改进,以期改进算法的迭代时间。     

求解TSP问题的一种改进蚁群算法

TSP问题是典型的NP—hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法,利用遗传算法生成信息素的分布,克服了蚁群算法中搜索时间长的缺陷。此外,在蚁群算法寻优中,采用交叉和变异的策略,改善了TSP解的质量。仿真结果显示,改进的蚁群算法是有效的。     

基于构建基因库求解TSP问题的改进遗传算法

文章针对TSP问题设计了一种将基因库和遗传算法结合起来的新算法,该算法首先构建一个基因库,在单亲演化中利用基因库指导种群的进化方向,其次在此基础上采用单亲进化遗传算法中的基因重组操作,保留每次获得的最好解组成初始种群,最后采用顺序交叉算子进行群体演化。给出的实验结果显示,该算法所获得的解与最优解的相对误差都不超过2%,该算法的收敛速度和寻优能力明显优于该问题的单亲进化遗传算法。     

ACR原型系统的全局路径规划遗传算法研究

ACR(物品自动运送机器人 )的全局路径规划是一种特殊而又典型的机器人路径规划问题, 可转化为一种TSP问题. 通过深入分析问题自身特性并辅以大量的仿真实验, 对遗传算法的选择、交叉、变异等操作及其相关参数作了深入细致的优化, 同时将“进化逆转”操作引入标准遗传算法框架中, 最终获得了一种性能良好的全局路径规划算法. 仿真结果表明, 此算法可在较短时间内求得最优解或准最优解.     

一种基于构建基因库求解TSP问题的遗传算法

传统的遗传算法通常被认为是自适应的随机搜索算法．该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge-GA)．该算法利用基因库指导种群的进化方向，并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的“探测”和“开发”能力．Ge-GA算法大大加快了遗传算法的收敛速度和寻优能力．作者测试了TSPLIB中的多个实例(城市数目从70～1577)，试验结果与最优解的误差都不超过0．001％．特别是对于难求解的TSP问题，如att532和fl1577，都能够在理想的时间内找到最优解．     

基于分布估计算法的喷涂机器人路径组合优化

针对喷涂机器人离线轨迹规划系统中路径顺序与喷涂方向同时影响喷涂效率的特点,将喷涂路径的组合与排序问题建模成开环式广义旅行商问题,并建立了相应的代价矩阵与优化目标;提出了一种基于分布式估计的路径组合优化算法,该算法在遗传算法中引入统计学习的手段,采用基于概率的模型学习和采样算法实现更好的进化效率,从而能够更加有效地获得全局最优解。通过多组数据的仿真,验证了该算法解决路径组合问题的有效性与可行性。     

基于最优解收集的扩展式并行遗传算法

在扩展分布式遗传算法(EDGA)的基础上提出了一种新的基于最优解收集的扩展式并行遗传算法(EPGA)。在该算法中，群体被划分为子群分配给各子处理单元(PE)计算，根处理器则在采用全局搜索策略进行搜索的同时，不断地从各子处理单元上收集局部最优解替换当前群体以获取较好的最优解。该算法采用子群的概念去获得较好的加速比，采用全局搜索策略的概念去获得较好的最优解，同时具有EDGA不具有的许多优点。给出了该算法针对经典的TSP问题的非阻塞MPI实现。实验表明该算法可以有效地提高遗传算法的加速比及增加获得最优解的概率。     

蚁群算法求解带约束火焰切割路径优化问题

火焰切割路径优化的主要目的是控制切割路径不当引起的热变形误差并对路径长度寻优。通过零件位置关系动态定义切割过程中的可选打孔点集合,将热变形约束条件量化;引入虚拟结点并定义距离矩阵,将路径规划转化为动态描述的TSP问题;基于蚁群算法提出约束条件下增大解空间的方法和信息素更新策略。实验结果表明,改进后的蚁群算法能够有效控制问题的规模并且得到更高质量的解,对热变形约束条件下的数控火焰切割路径优化有较好的效果和实用性。     

基于组合拆分策略求解TSP的动态规划算法

针对传统动态规划算法只能解决小规模旅行商问题(TSP)的不足,提出一种基于组合拆分策略的动态规划算法,通过5种不同的拆分策略将TSP序列拆分成若干段子序列,利用动态规划方法将子序列优化组合成新的TSP序列,重复该过程直到获得最优解散解。仿真结果表明,该算法能有效减小误差率,求解精确度较高,具有较低的计算复杂度和较好的稳健性。     

基于自组织优化算法的一类多旅行商问题

多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。     

基于最小生成1-树动态候选集的蚁群算法

利用旅行商问题中最优路径和生成树之间的关系,论文将最小生成1-树的概念引入蚁群算法,并提出一种新的量度来构造动态候选集。通过数据实验,表明该算法不仅有效地防止了解的退化,而且提高了搜索精度,收敛性有了明显改善。     

基于 Kinect 的拉普拉斯网格形变三维人脸建模

为了快速创建真实感较强的三维人脸模型,提出了基于 Kinect 的拉普拉斯网格形 变建模方法。利用 Kinect 获取彩色和深度图像信息,对深度图像进行双边滤波处理,对彩色图 像进行低层级顶点定位;构建标准三维人脸模型,并为该人脸模型中的顶点建立低、中、高 3 个级别的层级结构,通过低、中层级中顶点的位置关系创建 Sibson 局部坐标约束;利用该约束 构建彩色图像中间层级顶点,并结合深度信息对标准三维人脸模型进行拉普拉斯网格变形,获 得真实感较强的三维人脸模型。实验结果表明,该算法在建模的真实感上得到了提高,与对比 算法相比,在建模时间上得到很大的优化。     

汽车零部件立体仓库货位优化问题研究

以立体仓库库存为研究对象,从物流仓储管理角度,研究了货位分配优化问题。分 析了汽车零部件货位布局优化原则,建立多目标货位分配优化数学模型,对遗传算法进行了算子 设计,运用Matlab 软件实现模型的求解,得出可行的货位优化方案。最后结合实例进行多目标 货位优化数学模型求解及应用,并以三维仿真图形展示了优化效果,验证了所设计的遗传算法的 有效性,对同类问题的解决具有参考意义。     

基于汉明距离的改进粒子群算法求解旅行商问题

针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。     

Polyhedral Feasible Set Computation of MPC-Based Optimal Control Problems

Feasible sets play an important role in model predictive control (MPC) optimal control problems (OCPs). This paper proposes a multi-parametric programming-based algorithm to compute the feasible set for OCP derived from MPC-based algorithms involving both spectrahedron (represented by linear matrix inequalities) and polyhedral (represented by a set of inequalities) constraints. According to the geometrical meaning of the inner product of vectors, the maximum length of the projection vector from the feasible set to a unit spherical coordinates vector is computed and the optimal solution has been proved to be one of the vertices of the feasible set. After computing the vertices, the convex hull of these vertices is determined which equals the feasible set. The simulation results show that the proposed method is especially efficient for low dimensional feasible set computation and avoids the non-unicity problem of optimizers as well as the memory consumption problem that encountered by projection algorithms.      

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

In this paper, a memetic algorithm with competition (MAC) is proposed to solve the capacitated green vehicle routing problem (CGVRP). Firstly, the permutation array called traveling salesman problem (TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor (kNN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search (VNS) framework and the simulated annealing (SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station (AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-of-experiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.      

An integrated model for solving cell formation and cell layout problem simultaneously considering new situations

Cellular manufacturing system (CMS) is one of the group technology (GT) usages. Among the necessary decisions for a successful CMS implementation, cell formation problem (CFP) and cell layout problem (CLP) are two most popular ones. The majority of past studies in CMS discussed on CFPs and some of those focused on CLP ones. A few researchers solve the CPF and CLP simultaneously. In this paper, we present a new integrated mathematical model considering cell formation and cell layout simultaneously. The goal of our model is to group similar parts and corresponding different machines in same cells. Machines sequence in each cell and cell positions is also specified in the system. Moreover, our proposed model considers forward and backtracking movements as well as new assumptions for distances between cells using sequence data and production volume. One appropriate adjusted measure from the literature and two new measures of performance for evaluating solutions are defined. To validate the model, two well-known critical benchmark examples are employed. Computational experiments demonstrate that our proposal is a proficient model and show the effectiveness of our implementation.