检索结果-内蒙古大学图书馆

An Extended Self-Organizing Map based on 2-opt algorithm for solving symmetrical Traveling Salesperson Problem

NEURAL COMPUTING & APPLICATIONS 2015年第4期26卷 987-994页

作者： Ahmad, Rashid Kim, DoHyeun Jeju Natl Univ Dept Comp Engn Jeju Si Jeju Do South Korea

Self-organizing map (SOM) is a powerful variant of neural network for solving optimization problems. Many researchers have reported SOM for Traveling Salesperson Problem;however, problems still exist due to the trapping of the optimization techniques at the local optimal position. In this work, we propose an Extended Self-Organizing Map based on 2-opt algorithm with one-dimensional neighborhood to approach the Symmetrical Traveling Salesperson Problem (STSP). We elaborate our approach for STSP where weights of neurons represent nodes that are placed in the polygonal domain. The selection of winner neuron of SOM has been extended to overcome the problem of trapping of SOM at local optima. The results of SOM are improved through 2-opt local optimization algorithm. We briefly discuss self-organization in neural networks, 2-opt algorithm, and extension applied to SOM. Finally, the algorithm is compared with Kohonen Self-Organizing Map and Evolutionary algorithm. The results show that our approach performs better as compared to other techniques.

关键词： Artificial neural network Self-Organizing Maps Symmetrical Traveling Salesperson Problem 2-opt algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Hybrid Method Based on Nearest Neighbor algorithm and 2-opt algorithm for Traveling Salesman Problem 4

A New Hybrid Method Based on Nearest Neighbor Algorithm and ...

引用

4th International Conference on Wireless and Telematics (ICWT)

作者： Nuraiman, Dian Dewi, Yushinta Ilahi, Fadilah Hamidi, Eki Ahmad Zaki UIN Sunan Gunung Djati Dept Math Bandung Indonesia UIN Sunan Gunung Djati Dept Elect Engn Bandung Indonesia

ISBN: (纸本)9781538661635

Traveling salesman problem has been one of the mostly studied problems in combinatorial optimization. This paper proposes a new hybrid method combining the nearest neighbor algorithm and the 2-opt algorithm. The performance of this method has been tested to several benchmark problems from TSPLIB involving 11 instances of symmetric problems and three instances of asymmetric problems with various number of nodes from 17 to 783 nodes. The results show that the hybrid method can reduce the relative error significantly compared to the nearest neighbor algorithm only.

关键词： traveling salesman problem nearest neighbor algorithm 2-opt algorithm hybrid method

来源：评论

学校读者我要写书评

暂无评论

Trip Itinerary Generation with 2-opt algorithm 22

Trip Itinerary Generation with 2-Opt Algorithm

引用

Proceedings of the 4th International Conference on Advanced Information Science and System

作者： Omar Challaf Sook-Ling Chua Lee Kien Foo Faculty of Computing and Informatics Multimedia University Malaysia

ISBN: (纸本)9781450397933

Advances in digital technologies and communications are impacting how people travel. However, there are still lacking of personalised digital-based tools to support people in trip planning. Although there are a number of widely used trip planner applications, these applications may not be effective in generating trip itinerary as they do not take into account of user trip preferences and the total travel time to spend. In this paper, we proposed a heuristic search algorithm based on 2-opt to generate trip itinerary. A proof of concept mobile application for trip planning is developed to demonstrate the validity of our method.

关键词： 2-opt algorithm Trip Planning Trip Itinerary Generation

来源：评论

学校读者我要写书评

暂无评论

Discrete artificial ecosystem-based optimization for spherical capacitated vehicle routing problem

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2023年第13期83卷 37315-37350页

作者： Tang, Jiaju Luo, Qifang Zhou, Yongquan Guangxi Univ Nationalities Coll Artificial Intelligence Nanning 530006 Peoples R China Guangxi Univ Nationalities Xiangsihu Coll Nanning 530225 Peoples R China Guangxi Key Labs Hybrid Computat & IC Design Anal Nanning 530006 Peoples R China

The capacity constrained vehicle routing problem (CVRP) is one of the most well-known combinatorial optimization problems. Many studies have proposed various methods to solve the two-dimensional CVRP problem. In this paper, we firstly extend the CVRP problem to a three-dimensional space, called SCVRP, where all customers are distributed on a sphere. Secondly, a discrete artificial ecosystem-based optimization algorithm (DAEO) is proposed to solve the SCVRP problem. DAEO uses five local search operators to discretize the position update formula of the original AEO algorithm and introduces the 2-opt algorithm to simulate the mutation mechanism of organisms in the ecosystem. Furthermore, to evaluate the performance of the proposed algorithm, 32 test instances are designed, having 25-400 customers. These instances take into account factors such as customer position and demand distribution to be closer to the actual situation. The experimental results show that the proposed algorithm has good feasibility and competitiveness in solving the SCVRP problem, and can obtain better solutions than other intelligent algorithms.

关键词： Capacitated vehicle routing problem artificial ecosystem-based optimization Local search operators 2-opt algorithm Spherical CVRP

来源：评论

学校读者我要写书评

暂无评论

An Improved Ant Colony optimization for Solving Task Scheduling Problem in Radar Signal Processing System

引用

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2023年第2-3期95卷 333-350页

作者： Xu, Guowei Lin, Hui Cheng, Yi Li, Shuo Tiangong Univ Sch Control Sci & Engn Tianjin 300387 Peoples R China Tiangong Univ Sch Mech Engn Tianjin 300387 Peoples R China Tiangong Univ Key Lab Adv Elect Engn & Energy Technol Tianjin 300387 Peoples R China

In order to solve the problem of low efficiency and high error rate in the manual establishment of the logical relationship mapping table, this paper proposes an implementation method for automatically establishing a mapping relation table based on Ant Colony System (ACS), and writes a corresponding GUI development environment based on Qt. Aiming at the shortcomings of ACS algorithm such as slow convergence and easy to fall into local optimal, the pheromone volatilization factor and expected heuristic factor of ACS are adaptively improved in this paper, and then the search strategy of 2-opt algorithm is integrated to make ACS jump out of the local optimal solution and improve the accuracy of mapping result. The experimental results show that the proposed algorithm can search for the optimal mapping scheme to satisfy the constraints. The quality and generation speed of the mapping scheme have been greatly improved compared to manual establishment methods, which can effectively improve the performance of the radar signal processing system.

关键词： Radar signal processing Task scheduling Ant colony system (ACS) 2-opt algorithm Logical relationship mapping table

来源：评论

学校读者我要写书评

暂无评论

Discrete Salp Swarm algorithm for Euclidean Travelling Salesman Problem

引用

APPLIED INTELLIGENCE 2023年第10期53卷 11420-11438页

作者： Panwar, Karuna Deep, Kusum Indian Inst Technol Roorkee Dept Math Roorkee Uttar Pradesh India

The Salp Swarm algorithm (SSA) is one of the recently proposed swarm intelligence-based algorithms, which finds its motivation in the swarming behaviour of salps when navigating and foraging in the ocean. The SSA is essentially derived to solve optimization problems that have continuous search space. SSA is a simple to implement and competitive algorithm that has been proven helpful in a variety of real-world applications. It has been explored over several optimization problems so far. In this study, an enhanced discrete version of SSA is proposed to solve the Travelling Salesman Problem (TSP). As TSP is a combinatorial optimization problem, the classical SSA is modified using swap, shift and symmetry operators for global exploration and local exploitation. Also, the 2-opt method has been incorporated with the proposed algorithm to improve the local search ability of the algorithm while addressing discrete problems. The proposed Discrete Salp Swarm algorithm (DSSA) has evaluated over 45 TSP instances, and the computational results showed that it is a promising algorithm. To assess its performance, the proposed algorithm's results are compared with well-known algorithms such as Genetic algorithm, Artificial Bee Colony, Spider Monkey algorithm, Jaya algorithm, Black Hole, Symbiotic Organism Search etc. The proposed algorithm significantly outperformed these algorithms for a majority of TSP instances.

关键词： Salp swarm algorithm Travelling salesman problem Combinatorial optimization problem Metaheuristics 2-opt algorithm

来源：评论

学校读者我要写书评

暂无评论

A 2-opt based differential evolution for global optimization

引用

APPLIED SOFT COMPUTING 2010年第4期10卷 1200-1207页

作者： Chiang, Cheng-Wen Lee, Wei-Ping Heh, Jia-Sheng Chung Yuan Christian Univ Dept Elect Engn Chungli 320 Taoyuan County Taiwan Chung Yuan Christian Univ Dept Management Informat Syst Chungli 320 Taoyuan County Taiwan

Differential evolution (DE) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problems. However, DE has shown some weaknesses, especially the long computational times because of its stochastic nature. This drawback sometimes limits its application to optimization problems. Therefore we propose the 2-opt based DE (2-opt DE) which is inspired by 2-opt algorithms to accelerate DE. The novel mutation schemes of 2-opt DE, DE/2-opt/1 and DE/2-opt/2 are substituted for mutation schemes of the original DE namely DE/rand/1 and DE/rand/2. We also provide a comparison of 2-opt DE to DE. A comprehensive set of 19 benchmark functions is employed for experimental verification. The experimental results confirm that 2-opt DE outperforms the original DE in terms of solution accuracy and convergence speed. Crown Copyright (C) 2010 Published by Elsevier B. V. All rights reserved.

关键词： 2-opt algorithm Differential evolution optimization

来源：评论

学校读者我要写书评

暂无评论

Parallel heuristic local search algorithm on OTIS hyper hexa-cell and OTIS mesh of trees optoelectronic architectures

引用

APPLIED INTELLIGENCE 2019年第2期49卷 661-688页

作者： Al-Adwan, Aryaf Sharieh, Ahmad Mahafzah, Basel A. Univ Jordan King Abdullah II Sch Informat Technol Comp Sci Dept Amman 11942 Jordan

Heuristic local search algorithms have achieved good results in tackling combinatorial optimization problems, such as Travelling Salesman Problem (TSP). One of the well-known local search algorithms is the 2-opt algorithm. As a local search algorithm, 2-opt has achieved approximate optimal solutions for TSP within a reasonable time, especially for small data instances. However, solving large data instances of TSP using 2-opt requires extensive computation and considerable CPU time. Therefore, this paper presents a parallel version of the 2-opt algorithm, exploiting the features of optical Transpose Interconnection System (OTIS) in solving the TSP. In this paper, we present the Parallel Repetitive 2-opt (PRTO) algorithm for solving symmetric TSP on OTIS Hyper Hexa-Cell (OTIS-HHC) and OTIS Mesh of Trees (OTIS-MOT) optoelectronic architectures. We assess the performance of our algorithm analytically in terms of parallel time complexity, speedup, efficiency, cost, and communication cost on both optoelectronic architectures. Furthermore, a set of simulation experiments is conducted on various instances from the standard TSP library. The simulation results confirm that our algorithm is efficient regarding speedup and efficiency. For instance, the PRTO algorithm achieves a speedup of 32.9 for 6880 cities over OTIS-HHC with 36 processors. Moreover, the superiority of PRTO algorithm is shown through solving the TSP on OTIS-HHC and OTIS-MOT;its performance has been compared with the performance of the Parallel Repetitive Nearest Neighbor (PRNN) algorithm in terms of speedup, efficiency, and solution quality. For example, as a best case, the PRTO algorithm has shown 34 times improved speedup over the PRNN algorithm.

关键词： Local search algorithm 2-opt algorithm Repetitive nearest neighbor algorithm Travelling salesman problem Interconnection network optoelectronic architecture

来源：评论

学校读者我要写书评

暂无评论

Discrete Marine Predators algorithm for Symmetric Travelling Salesman Problem

引用

EVOLUTIONARY INTELLIGENCE 2024年第5-6期17卷 3833-3848页

作者： Kumar, Manish Panwar, Karuna Deep, Kusum Indian Inst Technol Roorkee Dept Math Roorkee 247667 Uttarakhand India Indian Inst Technol Roorkee Mehta Family Sch Data Sci & Artificial Intelligenc Roorkee 247667 Uttarakhand India

This paper addresses the well-known NP-hard problem, the Symmetric Travelling Salesman Problem (STSP), which has numerous applications in logistics and graph theory. To solve this complex problem, a discrete version of the Marine Predators algorithm (D-MPA) is introduced. Although MPA has been extensively studied for various optimization problems and real-world applications, its use in routing problems, particularly TSP, remains relatively unexplored. To adapt MPA for STSP, the positions of individuals are initially updated using the classical MPA algorithm. The continuous values generated by the classical MPA are then converted to discrete values, followed by the application of a permutation operator to maintain diversity in the population. In addition, a local search algorithm, 2-opt, is applied to further improve the results for STSP instances. The effectiveness of the proposed algorithm is demonstrated on STSP benchmark instances of sizes ranging from 14 to 439. The performance of D-MPA is compared against several existing algorithms, including the Genetic algorithm (GA), Bat algorithm (BA), Discrete Firefly algorithm (DFA), Evolutionary Simulated Annealing (ESA), Island-Based Distributed Genetic algorithm (IDGA), Discrete Imperialist Competitive algorithm (DICA), and Discrete Grey Wolf optimization (DGWO). To ensure an unbiased and rigorous comparison, descriptive statistics such as mean and standard deviation are used, and a Wilcoxon Signed-Rank test is conducted for statistical validation. The results demonstrate that D-MPA not only competes, but also consistently outperforms these algorithms, making it a valuable resource for the research community.

关键词： Travelling Salesman Problem Metaheuristic algorithm Marine Predators algorithm 2-opt algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved 2-opt optimisation scheme for Hamilton loop

引用

INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS IN TECHNOLOGY 2020年第2期64卷 151-157页

作者： Bo, Sun Shicai, Lu Yongquan, You Chuanxiang, Ren Shandong Univ Sci & Technol Coll Intelligent Equipment Taian Jinan 271000 Shandong Peoples R China Shandong Univ Sci & Technol Sch Elect Informat Engn Taian Jinan 266590 Shandong Peoples R China Shandong Univ Sci & Technol Coll Transportat Taian Jinan 266590 Shandong Peoples R China

Aiming at the problem that the traditional traffic route planning has a single target strategy and cannot be adjusted according to the actual situation, a multi-lane planning model based on Hamilton loops is proposed, which uses the characteristics of Hamilton loops to cover all nodes in the set and uses the nearest neighbour algorithm to obtain the initial loop. The improved 2-opt algorithm avoids the problem caused by randomness and improves the efficiency of 2-opt algorithm. In the case of considering road congestion, the introduction of speed parameters and comprehensive influence factors can give different path planning schemes according to different actual situations, and find the shortest time path and the shortest path, which makes Hamilton loop model more practical. The simulation results verify that the improved model can meet different planning requirements, achieve more targeted path planning, optimise the path planning scheme, and enhance people's travel efficiency.

关键词： Hamilton loop 2-opt algorithm path planning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：