Font Size: a A A

Research On Ant Colony Algorithm For Travelling Salesman Problem And Image Segmentation

Posted on:2021-05-26Degree:MasterType:Thesis
Country:ChinaCandidate:Z Q ZhangFull Text:PDF
GTID:2428330611998161Subject:Computer technology
Abstract/Summary:PDF Full Text Request
Nowadays,as the amount of data increases,the number of optimization problems is increasing,and the swarm intelligence algorithm provides a certain idea for solving optimization problems.As a kind of swarm intelligence algorithm,ant colony algorithm can effectively deal with optimization problems such as combination and clustering.The TSP as a representative of combinatorial optimization problems and the image segmentation as a representative of clustering problems have been extensively studied in recent years.However,the ant colony algorithm is relatively fixed when solving the TSP,and it runs slower when solving the image segmentation,which needs to be further improved.Therefore,this article is divided into two parts: the research on ant colony algorithm for TSP and the research on ant colony algorithm for image segmentation.This thesis proposes a method of combining reduction thought and ant colon y algorithm to divide the TSP and the image segmentation into many sub-problems for solving,which provides a new idea for solving the TSP and can effectively improve the running speed of the image segmentation.In this thesis,the convex hull reduction method of TSP is proposed,which provides a new way of solving TSP.Make the convex hull of the TSP point set,divide the points in the convex hull according to the degree of membership to the classification of the convex hull edge,all the points in each classification constitute a subset,and the TSP is also reduced to multiple constrained sub problems,recursively solve sub-problems,and combine all sub-problems to form the original problem.Two sub-set division methods are proposed,single-layer convex hull division method and hierarchical convex hull division method,and tested on the TSPlib dataset to verify the effectiveness of the TSP convex hull reduction method.To study the ant colony algorithm for TSP,a convex hull reduction method based on ant colony algorithm for TSP is proposed.The points in the convex hull are classified into various subsets used the idea that the ant colony algorithm is used to solve the clustering problem.Using the traditional ant colony algorithm to solve the TSP problem and constructing the route from city to city to solve the constrained sub-problems formed by each subset.Finally combine the solutions of each sub-problem to form the solution of the original problem.The experiment tested the effects of two heuristic functions and related parameter settings on the quality of the solution,and compared with the ant system and ant colony system to confirm the feasibility of the method.To study the ant colony algorithm for image segmentation,an image segmentation method based on reduction thought and ant colony algorithm is proposed.Using reduction thought to divide the image into multiple sub-images,using ant colony algorithm to segment each sub-image to form superpixels,and then using the ant colony algorithm to merge each superpixel to form the whole image segmentation.The experiment tested the influence of spatial information,pheromones update formula and the number of sub-image blocks on the image segmentation quality,and successfully combined this method with fuzzy C-means clustering algorithm,which can effectively improve the running speed of algorithm for image segmentation.
Keywords/Search Tags:ant colony algorithm, travelling salesman problem, image segmentation, redunction thought, cluster analysis
PDF Full Text Request
Related items