A Scheme Library-Based Ant Colony Optimization with 2-Opt Local Search for Dynamic Traveling Salesman Problem

The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant colony optimization(ACO)with a two-optimization(2-opt)strategy to solve the DTSP efficiently.The work is novel and contributes to three aspects:problemmodel,optimization framework,and algorithmdesign.Firstly,in the problem model,traditional DTSP models often consider the change of travel distance between two nodes over time,while this paper focuses on a special DTSP model in that the node locations change dynamically over time.Secondly,in the optimization framework,the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment.The framework of offline optimization and online application is proposed due to the fact that the environmental change inDTSPis caused by the change of node location,and therefore the newenvironment is somehowsimilar to certain previous environments.This way,in the offline optimization,the solutions for possible environmental changes are optimized in advance,and are stored in a mode scheme library.In the online application,when an environmental change is detected,the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity.Thirdly,in the algorithm design,the ACO cooperates with the 2-opt strategy to enhance search efficiency.To evaluate the performance of ACO with 2-opt,we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms.The experimental results show that ACO with 2-opt can solve the DTSPs effectively.

An Efficient Allocation for Lung Transplantation Using Ant Colony Optimization

A relationship between lung transplant success and many features of recipients’/donors has long been studied.However,modeling a robust model of a potential impact on organ transplant success has proved challenging.In this study,a hybrid feature selection model was developed based on ant colony opti-mization(ACO)and k-nearest neighbor(kNN)classifier to investigate the rela-tionship between the most defining features of recipients/donors and lung transplant success using data from the United Network of Organ Sharing(UNOS).The proposed ACO-kNN approach explores the features space to identify the representative attributes and classify patients’functional status(i.e.,quality of life)after lung transplantation.The efficacy of the proposed model was verified using 3,684 records and 118 input features from the UNOS.The developed approach examined the reliability and validity of the lung allocation process.The results are promising regarding accuracy prediction to be 91.3%and low computational time,along with better decision capabilities,emphasizing the potential for automatic classification of the lung and other organs allocation pro-cesses.In addition,the proposed model recommends a new perspective on how medical experts and clinicians respond to uncertain and challenging lung alloca-tion strategies.Having such ACO-kNN model,a medical professional can sum-marize information through the proposed method and make decisions for the upcoming transplants to allocate the donor organ.

Route Search Method for Railway Replacement Buses Adopting Ant Colony Optimization

In recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population. Therefore, it is best to consider the discontinuation of local railway lines and introduce replacement buses to secure the transportation methods of the local people especially in rural areas. Based on the above background, targeting local railway lines that may be discontinued in the near future, appropriate bus stops when provided with potential bus stops were selected, the present study proposed a method that introduces routes for railway replacement buses adopting ant colony optimization (ACO). The improved ACO was designed and developed based on the requirements set concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as well as the constraint conditions concerning the route length, number of turns and zones without bus stops. Original road network data were generated and processed adopting a geographic information systems (GIS), and these are used to search for the optimal route for railway replacement buses adopting the improved ACO concerning the 8 zones on the target railway line (JR Kakogawa line). By comparing the improved ACO with Dijkstra’s algorithm, its relevance was verified and areas needing further improvements were revealed.

Optimization of Fairhurst-Cook Model for 2-D Wing Cracks Using Ant Colony Optimization (ACO), Particle Swarm Intelligence (PSO), and Genetic Algorithm (GA)

The common failure mechanism for brittle rocks is known to be axial splitting which happens parallel to the direction of maximum compression. One of the mechanisms proposed for modelling of axial splitting is the sliding crack or so called, “wing crack” model. Fairhurst-Cook model explains this specific type of failure which starts by a pre-crack and finally breaks the rock by propagating 2-D cracks under uniaxial compression. In this paper, optimization of this model has been considered and the process has been done by a complete sensitivity analysis on the main parameters of the model and excluding the trends of their changes and also their limits and “peak points”. Later on this paper, three artificial intelligence algorithms including Particle Swarm Intelligence (PSO), Ant Colony Optimization (ACO) and genetic algorithm (GA) has been used and compared in order to achieve optimized sets of parameters resulting in near-maximum or near-minimum amounts of wedging forces creating a wing crack.

基于ACO-USK优化VMD参数的滚动轴承故障诊断研究

传统变分模态分解(VMD)技术需要人为主观预设模态分解个数K和二次惩罚因子α,由此可能导致信号的欠分解、过分解、模态混叠或信息丢失等问题,从而影响对滚动轴承早期故障信号的分解效果。本文根据峭度指标对滚动轴承早期故障异常敏感的特点,提出了一种以联合平方峭度(USK)指标为目标函数,结合蚁群优化(ACO)算法的ACO-USK优化方法,对VMD模态分解个数K和二次惩罚因子α进行自适应寻优。研究结果表明:对于滚动轴承早期故障信号,与以包络熵(EE)为目标函数的VMD优化方法对比,本文提出的方法既具有较好的包络谱信噪比(SNRES),又有在计算用时上的优越性,具有一定的工程应用价值。

Max-Min Adaptive Ant Colony Optimization Approach to Multi-UAVs Coordinated Trajectory Replanning in Dynamic and Uncertain Environments

Multiple Uninhabited Aerial Vehicles (multi-UAVs) coordinated trajectory replanning is one of the most complicated global optimum problems in multi-UAVs coordinated control. Based on the construction of the basic model of multi-UAVs coordinated trajectory replanning, which includes problem description, threat modeling, constraint conditions, coordinated function and coordination mechanism, a novel Max-Min adaptive Ant Colony Optimization (ACO) approach is presented in detail. In view of the characteristics of multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments, the minimum and maximum pheromone trails in ACO are set to enhance the searching capability, and the point pheromone is adopted to achieve the collision avoidance between UAVs at the trajectory planner layer. Considering the simultaneous arrival and the air-space collision avoidance, an Estimated Time of Arrival (ETA) is decided first. Then the trajectory and flight velocity of each UAV are determined. Simulation experiments are performed under the complicated combating environment containing some static threats and popup threats. The results demonstrate the feasibility and the effectiveness of the proposed approach.

Hybrid ant colony optimization for the resource-constrained project scheduling problem

To solve the resource-constrained project scheduling problem （RCPSP）, a hybrid ant colony optimization （HACO） approach is presented. To improve the quality of the schedules, the HACO is incorporated with an extended double justification in which the activity splitting is applied to predict whether the schedule could be improved. The HACO is tested on the set of large benchmark problems from the project scheduling problem library （PSPLIB）. The computational result shows that the proposed algo- rithm can improve the quality of the schedules efficiently.

An effective multi-level algorithm based on ant colony optimization for graph bipartitioning

Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration （VLSI） design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant＇s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute （ANSI） C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.

Extraction of affine invariant features for shape recognition based on ant colony optimization

A new approach to extraction of affine invariant features of contour image and matching strategy is proposed for shape recognition.Firstly,the centroid distance and azimuth angle of each boundary point are computed.Then,with a prior-defined angle interval,all the points in the neighbor region of the sample point are considered to calculate the average distance for eliminating noise.After that,the centroid distance ratios（CDRs） of any two opposite contour points to the barycenter are achieved as the representation of the shape,which will be invariant to affine transformation.Since the angles of contour points will change non-linearly among affine related images,the CDRs should be resampled and combined sequentially to build one-by-one matching pairs of the corresponding points.The core issue is how to determine the angle positions for sampling,which can be regarded as an optimization problem of path planning.An ant colony optimization（ACO）-based path planning model with some constraints is presented to address this problem.Finally,the Euclidean distance is adopted to evaluate the similarity of shape features in different images.The experimental results demonstrate the efficiency of the proposed method in shape recognition with translation,scaling,rotation and distortion.

Efficiency improvement of ant colony optimization in solving the moderate LTSP

In solving small- to medium-scale travelling salesman problems （TSPs） of both symmetric and asymmetric types, the traditional ant colony optimization （ACO） algorithm could work well, providing high accuracy and satisfactory efficiency. However, when the scale of the TSP increases, ACO, a heuristic algorithm, is greatly challenged with respect to accuracy and efficiency. A novel pheromone-trail updating strategy that moderately reduces the iteration time required in real optimization problem-solving is proposed. In comparison with the traditional strategy of the ACO in several experiments, the proposed strategy shows advantages in performance. Therefore, this strategy of pheromone-trail updating is proposed as a valuable approach that reduces the time-complexity and increases its efficiency with less iteration time in real optimization applications. Moreover, this strategy is especially applicable in solving the moderate large-scale TSPs based on ACO.

Ant Colony Optimization Based on Adaptive Volatility Rate of Pheromone Trail

Ant colony optimization (ACO) has been proved to be one of the best performing algorithms for NP-hard problems as TSP. The volatility rate of pheromone trail is one of the main parameters in ACO algorithms. It is usually set experimentally in the literatures for the application of ACO. The present paper first proposes an adaptive strategy for the volatility rate of pheromone trail according to the quality of the solutions found by artificial ants. Second, the strategy is combined with the setting of other parameters to form a new ACO method. Then, the proposed algorithm can be proved to converge to the global optimal solution. Finally, the experimental results of computing traveling salesman problems and film-copy deliverer problems also indicate that the proposed ACO approach is more effective than other ant methods and non-ant methods.

基于Dijkstra-ACO混合算法的煤矿井下应急逃生路径动态规划

煤矿井下应急逃生路径规划需要根据煤矿井下环境的变化及时调整,但传统方法依赖静态网络和固定权重而无法实现逃生路径规划适应井下环境动态变化。针对上述问题,提出了一种基于Dijkstra-ACO(蚁群优化)混合算法的煤矿井下应急逃生路径动态规划方法。基于巷道坡度和水位对逃生的影响分析,建立了煤矿井下应急逃生最优路径动态规划模型,实现逃生路径随巷道坡度、水位等环境变化而实时调整,从而提高逃生效率和安全性。采用Dijkstra-ACO混合算法求解煤矿井下应急逃生最优路径动态规划模型,即利用Dijkstra算法快速确定初始路径,引入ACO算法寻找距离最短且安全性最高的逃生路径,实现规划路径能够适应环境变化。搭建了模拟某煤矿多种巷道类型及其坡度、水位等参数的仿真环境,开展了应急逃生路径动态规划实验。结果表明,在50 m×100 m,100 m×200 m,150 m×250 m 3种不同尺寸的测试区域中,基于Dijkstra-ACO混合算法规划的路径长度比基于A^(*)算法和基于改进蚁群算法规划的路径长度缩短了19%以上,同时避障率提高了5%以上。

Optimizing Inter Cluster Ant Colony Optimization Data Aggregation Algorithm with Rendezvous Nodes and Mobile Sink

Energy conservation is becoming the main critical issue in wireless sensor network and also the main research area for most of the researchers. For improving the energy efficiency, sink mobility is used with constrain path in wireless sensor network. In order to solve these optimization problems, inter cluster Ant Colony Optimization Algorithm (ACO) is used with mobile sink (MS) and rendezvous nodes (RN). The proposed algorithm will improve 30% more network lifetime than the existing algorithm and prompts high accurate delivery of packets in highly dense network.

Differential Evolution Immunized Ant Colony Optimization Technique in Solving Economic Load Dispatch Problem

Since the introduction of Ant Colony Optimization (ACO) technique in 1992, the algorithm starts to gain popularity due to its attractive features. However, several shortcomings such as slow convergence and stagnation motivate many researchers to stop further implementation of ACO. Therefore, in order to overcome these drawbacks, ACO is proposed to be combined with Differential Evolution (DE) and cloning process. This paper presents Differential Evolution Immunized Ant Colony Optimization (DEIANT) technique in solving economic load dispatch problem. The combination creates a new algorithm that will be termed as Differential Evolution Immunized Ant Colony Optimization (DEIANT). DEIANT was utilized to optimize economic load dispatch problem. A comparison was made between DEIANT and classical ACO to evaluate the performance of the new algorithm. In realizing the effectiveness of the proposed technique, IEEE 57-Bus Reliable Test System (RTS) has been used as the test specimen. Results obtained from the study revealed that the proposed DEIANT has superior computation time.

Solving algorithm for TA optimization model based on ACO-SA

An ant colony optimization （ACO）-simulated annealing （SA）-based algorithm is developed for the target assignment problem （TAP） in the air defense （AD） command and control （C2） system of surface to air missile （SAM） tactical unit. The accomplishment process of target assignment （TA） task is analyzed. A firing advantage degree （FAD） concept of fire unit （FU） intercepting targets is put forward and its evaluation model is established by using a linear weighted synthetic method. A TA optimization model is presented and its solving algorithms are designed respectively based on ACO and SA. A hybrid optimization strategy is presented and developed synthesizing the merits of ACO and SA. The simulation examples show that the model and algorithms can meet the solving requirement of TAP in AD combat.

基于IAPF-ACO的工业机器人运动规划

针对蚁群算法运动规划收敛慢且精度不佳的问题,提出一种改进势场蚁群(improved artificial potential field ant colony optimization, IAPF-ACO)算法。斥力计算模型引入目标调节因子解决势场寻优不可达且易陷入局部最优问题。蚁群算法计算框架加入改进势场模型,即启发信息函数中增加势场信息因子。三维障碍物空间仿真规划表明:IAPF-ACO算法在离散环境与聚集环境规划路径质量较优、规划结果较为稳定。在MATLAB搭建工业机器人仿真模型,关节空间内对规划路径点平滑处理,避障仿真结果表明,工业机器人末端位移是一条安全、平滑的运动轨迹。

Safety Evaluation Method of Evacuation Routes in Areas in Case of Earthquake Disasters Using Ant Optimization Algorithm and Geographic Information Systems

The present study aims to propose the method for the quantitative evaluation of safety concerning evacuation routes in case of earthquake disasters in urban areas using ACO （Ant Colony Optimization） algorithm and GIS （Geographic Information Systems）. Regarding the safety evaluation method, firstly, the similarity in safety was focused on while taking into consideration road blockage probability, and after classifying roads by means of the hierarchical cluster analysis, the congestion rates of evacuation routes using ACO simulations were estimated. Based on these results, the multiple evacuation routes extracted were visualized on digital maps by means of GIS, and its safety was evaluated. Furthermore, the selection of safe evacuation routes between evacuation sites, for cases when the possibility of large-scale evacuation after an earthquake disaster is high, is made possible. As the safety evaluation method is based on public information, by obtaining the same geographic information as the present study, it is effective in other areas regardless of whether the information is of the past and future. Therefore, in addition to spatial reproducibility, the safety evaluation method also has high temporal reproducibility. Because safety evaluations are conducted on evacuation routes based on quantified data, highly safe evacuation routes that are selected have been quantitatively evaluated, and thus serve as an effective indicator when selecting evacuation routes.

基于GDACO算法的引导疏散路径规划研究

针对教学建筑内中人员疏散存在盲目、无序、效率低等问题,提出了双层蚁群路径规划算法(GDACO)引导人员疏散的路径规划。对环境栅格进行处理,增添危险栅格,使初始蚁群信息素呈阶梯式分布;提出双层蚁群算法,引导层蚁群通过全局搜索寻找引导路径,疏散层蚁群基于引导范围实现疏散路径寻优;进行路径优化处理,剔除冗余节点,对转折部分进行平滑处理。试验结果分析表明,所提GDACO算法能够减少路径转折点,规避风险路径,满足教学建筑内的引导疏散需求,规划路径符合实际疏散情况。

Precise Multi-Class Classification of Brain Tumor via Optimization Based Relevance Vector Machine

The objective of this research is to examine the use of feature selection and classification methods for distinguishing different types of brain tumors.The brain tumor is characterized by an anomalous proliferation of brain cells that can either be benign or malignant.Most tumors are misdiagnosed due to the variabil-ity and complexity of lesions,which reduces the survival rate in patients.Diagno-sis of brain tumors via computer vision algorithms is a challenging task.Segmentation and classification of brain tumors are currently one of the most essential surgical and pharmaceutical procedures.Traditional brain tumor identi-fication techniques require manual segmentation or handcrafted feature extraction that is error-prone and time-consuming.Hence the proposed research work is mainly focused on medical image processing,which takes Magnetic Resonance Imaging(MRI)images as input and performs preprocessing,segmentation,fea-ture extraction,feature selection,similarity measurement,and classification steps for identifying brain tumors.Initially,the medianfilter is practically applied to the input image to reduce the noise.The graph-cut segmentation technique is used to segment the tumor region.The texture feature is extracted from the output of the segmented image.The extracted feature is selected by using the Ant Colony Opti-mization(ACO)algorithm to improve the performance of the classifier.This prob-abilistic approach is used to solve computing issues.The Euclidean distance is used to calculate the degree of similarity for each extracted feature.The selected feature value is given to the Relevance Vector Machine(RVM)which is a multi-class classification technique.Finally,the tumor is classified as abnormal or nor-mal.The experimental result reveals that the proposed RVM technique gives a better accuracy range of 98.87%when compared to the traditional Support Vector Machine(SVM)technique.