Bionical Algorithms and Their Application on Function Ptimization and Multilevel Thresholding for Image Egmentation
|School||South China University of Technology|
|Course||Applied Computer Technology|
|Keywords||Bionical Algorithm Image Segmentation multilevel thresholding GeneticAlgorithm Estimation Of Distribution Algorithms Bayesian theorem Particle SwarmOptimization|
Optimization which has greatly influenced many disciplines and obtains rapid promotionand applications in so many engineering domains has received widespread attention as animportant scientific branch. Optimization has become an indispensable tool for many differentareas. Many optimization problems have been proved to be NP-Complete problems (NPC).So far there is no effective method of Polynomial time for NPC, and the computing time of atraditional optimization method grows exponentially with the scale of the problem. Thus,instead, researchers hoping to achieve optimal or near-optimal solutions in limited time havedeveloped a lot of Bionical algorithms such as, Genetic Algorithms, Estimation OfDistribution Algorithms, Particle Swarm Optimization, Tabu Search, hybrid optimizationstrategies and so on. This thesis focuses on Bionical Algorithms and Their Application onFunction Optimization and Multilevel Thresholding. The main works and innovative pointsare as follows:1) Traditional Genetic Algorithms initialize their individuals stochastically and generatetoo many eccentric and homogeneous individuals. This will cause premature convergence andslow down the speed. In this thesis this important problem is studied via thecomplementary-parent strategy of initializing population in PGA. We analyze it and concludethat the limiting probability of the traditional mutation operator based on this strategy is1/|HL|2higher than on the traditional one. This strategy is more efficient by applying toCoarse-grained parallel genetic algorithm which develops the parallelism among populations.For PGA, we also discuss the reproductive capacity of excellent schemata based on theschema theorem and demonstrate the global convergence using homogeneous finite Markovchain. And then, we present an improved algorithm named GACPS. With some of typicalunsymmetrical functions tested, simulation show the quality of GACPS is much higher thanPGA on precision, stability and convergence rate.2) Multilevel thresholding is an important technique for image compression, imageanalysis and pattern recognition. However, it is still a hard problem to determine the numberof thresholds automatically. So, a new multilevel thresholding method called as AutomaticMultilevel Thresholding Algorithm For Image Segmentation based on Block Sampling and Genetic Algorithm (AMT-BSGA), which can automatically determine the appropriate numberof thresholds and the proper threshold values, is proposed on the basis of Block Sampling andGenetic Algorithm. In AMT-BSGA, an image is treated as a population with the gray valuesof pixels as the individuals. First, an image is evenly divided into several blocks, and a sampleis drawn from each block. Then, genetic algorithm based optimizing is applied to each sampleso as to maximize the ratio of mean and variance for the sample. Based on the optimizedsamples, the number of thresholds and threshold values are preliminarily determined. Finally,a deterministic method is implemented to further optimize the number of thresholds andthreshold values. AMT-BSGA can work without knowing in advance other auxiliaryinformation, such as contextual or textual properties, and the number of thresholds. It has alower computing complexity which is almost independent from the number of thresholds andcan avoid the burden of analyzing histograms. AMT-BSGA can produce effective, efficientand smoother results, which has been verified by extensive simulations on Berkeley datasets.3) Based on Bayesian theorem and the probability distribution of promising solutionsand integrating with the basic principle of evolutionary computation, we proposes a novelalgorithm named Bayesian Forecasting Evolutionary Algorithm (BFEA). Our proposedmethod guides the exploration of the search space according to the prediction probability ofevery subspace including the optimal solutions. Moreover, prior information about theproblem is incorporated into the algorithm easily and much more information in the generatedpopulations is used. More importantly, BFEA is a new method to solve linkage problem anddeceptive problem effectively. This algorithm can converge faster to the subspaces withoptimal solution and its convergence, convergence rate and counteraction operator are alsoanalyzed theoretically. Theoretical analyses and tests have demonstrated the proposed methodhas a simpler algorithm model, lower computing complexity and higher computationaccuracy.4) A simpler and efficient PSO algorithm based on Bayesian theorem and the charactersof intensity images is proposed, called as Bayesian Particle Swarm Optimization algorithm(BPSO). In BPSO, a new method is designed to assign the constriction coefficient of the“social influence” term for each particle automatically and separately based on Bayesiantheorem, so that they can have different levels of exploration and exploitation capabilities. And a new population initialization strategy is adopted to make the search more efficient,according to the characters of multilevel thresholding in an image arranged from a low graylevel to a high one. The experimental results indicate that BPSO can produce effective,efficient and smoother segmentation results in comparison with three existing methods onBerkely datasets.