当前位置：搜档网 › Chaotic species based particle swarm optimization

Chaotic species based particle swarm optimization

Chaotic species based particle swarm optimization algorithms and its application in PCB components detection

Na Dong a ,b ,?,Chun-Ho Wu b ,Wai-Hung Ip b ,Zeng-Qiang Chen c ,Kai-Leung Yung b

School of Electrical Engineering and Automation,Tianjin Unversity,Tianjin 300072,China

Department of Industrial and Systems Engineering (ISE),The Hong Kong Polytechnic University,Hung Hom,Kln,Hong Kong,China c

Department of Automation,Nankai Unversity,Tianjin 300071,China

a r t i c l e i n f o Keywords:Chaos

Particle swarm optimization

Chaotic species based particle swarm optimization

Multimodal optimization Multi-template matching PCB components detection

a b s t r a c t

An improved particle swarm optimizer using the notion of chaos and species is proposed for solving a template matching problem which is formulated as a multimodal optimization problem.Template matching is one of the image comparison techniques.This technique is widely applied to determine the existence,location and alignment of a component within a captured image in the printed circuit board (PCB)industry where 100%quality assurance is always required.In this research,an ef?cient auto detection method using a multiple templates matching technique for PCB components detection is described.The new approach using chaotic species based particle swarm optimization (SPSO)is applied to the multi-template matching (MTM)process.To test its performance,the proposed Chaotic SPSO based MTM algorithm is compared with other approaches by using real captured PCB images.The Chaotic SPSO based MTM method is proven to be superior to other methods in both ef?ciency and effectiveness.

1.Introduction

Particle swarm optimization (PSO)(Kennedy &Eberhart,1995)is a newly developed evolutionary technique.Due to its simple concept,easy implementation,and quick convergence,nowadays,PSO has nowadays gained much attention and wide applications in different ?elds.For examples,Sun (2009)applied PSO to round-ness measurement under a machine vision system and Omran and Engelbrecht (2005)proposed a PSO-based image clustering meth-od.However,the standard PSO greatly depends on its parameters and exists as a premature phenomenon,especially in solving com-plex multi-hump problems (Angeline,1998).The notion of species based PSO (SPSO)was proposed by Li (2004),for solving multi-modal optimization problems.Chaos is a kind of characteristic of nonlinear systems and chaotic motion can traverse every state in a certain region by its own regularity,and nowadays,it has been applied in different ?elds (Jiang,Kwong,Chen,&Ysim,2012;Lu,Shieh,&Chen,2003;Wong,Kwok,&Law,2008;Zhao,Sun,Sun,&Jiang,2011).Due to the unique ergodicity and special ability in avoiding being trapped in local optima,chaos search is much high-er than some other stochastic algorithms (Li &Jiang,1998).Re-cently,several attempts for PSO using chaos methods were made (Liu,Wang,Jin,Tang,&Huang,2005;Song,Chen,&Yuan,2007;Xie,Zang,&Yang 2002)and obtained rich harvests.Xie et al.(2002)introduced chaos into the system by randomly reinitializing the particle positions with a small constant probability.Liu et al.(2005)incorporated chaos into PSO with adaptive inertia weight factor to construct a chaotic PSO.Song et al.(2007)combined tent map chaos with particle swarm optimization and proposed a new tent map chaotic particle swarm optimization (TCPSO).In this pa-per,the notion of chaos was introduced into the species based PSO and a novel Chaotic SPSO algorithm was proposed.The algorithm was analyzed on a test function and then applied into the compo-nents placement inspection of printed circuit boards (PCB).

Further research in multiple templates matching using the SPSO algorithm for PCB inspection has been undertaken recently (Wang,Wu,Ip,Chan,&Wang,2008;Wu et al.,2009).Normalized cross correlation (NCC)has been used as the similarity function in tem-plate matching.It has been proven to greatly reduce the data stor-age and also reduce the sensitivity in acquiring images when compared with traditional image subtraction,and hence enhances the robustness of the system (Moganti &Ercal,1996).Smaller com-ponents and greater component density are the two main elements affecting PCB inspection,but they are not the only ones.Speed al-ways restricts the performance for completing an inspection task.To satisfy the requirements in the inspection task,the proposed Chaotic SPSO is introduced into the detection of the PCB compo-nents.The effectiveness of the Chaotic SPSO algorithm in locating multiple components is fully illustrated through simulations and comparisons.

Section 2explains about the idea of multi-template matching method (MTM)and normalized cross correlation (NCC)value.

?Corresponding author at:School of Electrical Engineering and Automation,

Tianjin University,Tianjin 300072,China.Fax:+862227406272.

E-mail address:alinna1110@https://www.sodocs.net/doc/5b6202938.html, (N.Dong).

The concept of Chaotic SPSO,its simulation results in different benchmark tests,the formulation of the multiple template match-ing problem to a multimodal optimization problem and the idea of Chaotic SPSO for MTM are presented in Section3.The experimen-tal results of the proposed Chaotic SPSO based method for solving the PCB components detection problem are shown in Section4. Section5draws the conclusion.

2.Multi-template matching for components detection

Template matching can be used to?nd out how well a sub im-age(template image)matches the window of a captured image (Seul,O’Gorman,&Sammon,2000).The degree of matching is of-ten determined by evaluating the NCC value.The NCC has long been an effective similarity measurement method in feature matching.The basic idea of template matching is to loop the tem-plate through all the pixels in the captured image and compare the similarity.While this method is simple and easy to implement,it is the slowest method.To improve the ef?ciency of the correlation based template matching,the idea of multi-template matching (MTM)to solve such a problem was mooted.

In multi-template matching,at each point(x,y),the MTM_NCC value is de?ned as the maximum of a set of calculated NCC values which is obtained using corresponding templates. f is the average grey level intensity of the captured image region coincident with the k th template image. w k is the average grey level intensity of the k th template image.A‘‘perfect’’match between f and w k will result in a maximum value.For example,at point(x,y),NCC values are obtained through formula(1),NCC1is computed by using tem-plate1,and NCC2,calculated by using template2respectively.The MTM_NCC value at(x,y)can be obtained through formula(2):

NCCkex;yT?

P mà1

i?0

P nà1

j?0

fexti;ytjTà f

áwkei;jTà wk

P mà1

i?0

P nà1

j?0

?fexti;ytjTà f 2á

P mà1

P nà12

n o1=2

MTM NCCex;yT?max f NCC1ex;yT;NCC2ex;

3.Multimodal optimization for multiple problem

Multimodal optimization is used to

the searching space,rather than one and has been extensively studied by Antonopoulos,Bountis,&Vrahatis,2009). on a large variety of different techniques the literature.Among them,‘niches and

ing method(Goldberg,1987)were weakness of traditional evolutionary optimization.

Recently,a speciation based particle

od(Li,2004;Li,Balazs,Parks,&Clarkson, was introduced to solve multimodal

fact that speciation to PSO is a successful the global optima of a multimodal

to a peak of the?tness searching space, sub population of individuals that exhibits determined by particular metrics.The SPSO ple species within a population and

best for each species.The multiple species in parallel,and used to optimize multiple 3.1.Species based particle swam optimization

Central to the SPSO is the notion of species.A species can be de?ned as a group of individuals sharing common attributes accord-ing to some similarity metric.This similarity metric could be based on the Euclidean distance for genotypes using a real coded represen-tation,or the Hamming distance for genotypes with a binary repre-sentation.The smaller the Euclidean(or the Hamming)distance between two individuals,the more similar they are.The de?nition of species also depends on another parameter c s,which denotes the radius measured in Euclidean distance from the center of a spe-cies to its boundary.The center of a species,the so called species seed,is always the?ttest individual in the species.All particles that fall within the c s distance from the species seed are classi?ed as the same species.The particles start searching for the optimum of a gi-ven objective function by moving through the search space at a ran-dom initial position.The manipulation of the swarm can be represented by Eqs.(3)and(4).Eq.(3)updates the particle velocity and Eq.(4)updates each particle’s position in the search space, where x is the inertia weight,c1,c2are cognitive coef?cients and r1,r2are two uniform random numbers from U(0,1),p id is the per-sonal best position and l besti is the neighborhood best of particle i. V kt1

?x v k idtc1r1p k idàx k id

àá

tc2r2lbest k

àx k

e3T

x kt1

?x k

tv kt1ide4TOnce the species seeds have been identi?ed from the popula-tion,one can then allocate each seed to be the l best to all the parti-cles in the same species at each iteration step.The SPSO accommodating the algorithm for determining species seeds de-scribed above can be summarized in the following steps:

Step(1)Generate an initial population with randomly generated Fig.1.Distribution of the chaos variables.

12502N.Dong et al./Expert Systems with Applications39(2012)12501–12511

N.Dong et al./Expert Systems with Applications39(2012)12501–1251112503

In order to test the proposed Chaotic SPSO’s ability to locate multiple maxima,Himmelblau’s function is introduced as a test function:Fex;yT?200àex2tyà11T2àexty2à7T2e8TIt has two variables x and y,where-66x,y66.This function has four same global maxima which all equal to200at approxi-mately(à3.78,à3.28),(à2.815,3.125),(3.0,2.0)and(3.58,à1.86). Using SPSO and the proposed Chaotic SPSO respectively,the simu-lation results are shown as follows.

Here,we de?ne the swarm size as50,the inertia weight x=0.5, the cognitive coef?cients c1=c2=2for both the SPSO and the Cha-otic SPSO.As this simulation is to compare the results of Chaotic SPSO and SPSO under the same parameter settings,it is preferred to choose and?x the parameters as common ones according to several references and c s is given a moderate value2.0.Then,the following simulations are conducted.

(a)Run the SPSO for20iteration steps.The snapshot of the

searching process at the20th iteration is shown in Fig.4 on the left.

At the20th iteration,none of the maxima is found using the SPSO.The top four species seeds are:(à3.75,à3.27),(à2.75, 3.17),(2.97,1.95)and(3.58,à1.80).Their?tness values are 199.950,199.850,199.911and199.969respectively.

Then,run the Chaotic SPSO for20iteration steps.The snapshot of the searching process at the20th iteration is shown in Fig.4on the right.

Fig.4.Snapshot of the SPSO’s searching process at the20th iteration(left)and the Chaotic SPSO’s searching process at the20th iteration(right).

Table1

The maximal,the minimal and the mean iteration steps to locate all the maxima.

Algorithm Min.

iteration Max.

iteration

Successful

rate*(%)

Iteration(mean and

std.err.)

SPSO113177100130.57±10.22

Chaotic

SPSO

107158100127.97±9.01

*Successful rate means how many times that all maxima can be successfully located out of100runs.

Table2

The maximal,the minimal and the mean time to locate all the maxima100times successively during50runs.

Algorithm Min.run

time(s)Max.run

time(s)

Successful

rate*(%)

Time(mean and

std.err.)

SPSO 6.67 6.98100 6.78±0.07

Chaotic

SPSO

6.58 6.78100 6.69±0.05

*Successful rate means how many times that all maxima can be successfully located in the entire100serial times during50runs.

At the 20th iteration,none of the maxima is found using the Chaotic SPSO either.The top four species seeds here are:(à3.80,à3.29),(à2.80,3.13),(3.003,2.004)and (3.60,à1.87).Their ?t-ness values are 199.981,199.999,199.999and 199.977respectively.

It is obvious that in the Chaotic SPSO,the top four species seeds’?tness values are much closer to the maxima of Himmelblau’s function than the SPSO.

(b)This time,run the SPSO for 100iteration steps.The snapshot

of the searching process at the 100th iteration is shown in Fig.5on the left.At the 100th iteration,one of the maxima is found using the SPSO.There are four species seeds at the 100th iteration.They are:(à3.7793,à3.2832),(à2.8051,3.1313),(3.0000,2.0000)and (3.5844,à1.8481)respectively.

Then,run the Chaotic SPSO for 100iteration steps.The snapshot of the searching process at the 100th iteration is shown in Fig.5on the right.

At the 100th iteration,one of the maxima is found using the Chaotic SPSO,and there are six species seeds at the 100th iteration.They are:(à3.7793,à3.2832),(à2.8051,3.1313),(à1.7246,à2.5289),(3.0000,2.0000),(3.5844,à1.8481)and (4.6042,à4.0556)respectively,and the top 4seeds with bigger ?tness values are (à3.7793,à3.2832),(à2.8051,3.1313),(3.0000,2.0000)and (3.5844,à1.8481).

At the 100th iteration,the Chaotic SPSO can identify another two extra maxima besides the top 4maxima,which can fully illus-trate the better searching ability and greater searching power of the Chaotic SPSO.Thus,the Chaotic SPSO is a better means for solv-ing multi-hump problems.

(c)Run the SPSO and the Chaotic SPSO for 100independent

times respectively.The maximal,the minimal and the mean iteration steps to locate all the maxima are shown in Table 1.(d)Run the SPSO and the Chaotic SPSO for 50independent times

respectively.The maximal,the minimal and the mean of the total time to locate all the maxima in 100serial times are shown in Table 2.From Tables 1and 2,it can be seen clearly that the Chaotic SPSO is much faster and effective than the SPSO.3.3.Chaotic SPSO for MTM

When the MTM method is applied,it is clear that all objects can be matched with the corresponding template simultaneously,thus,the components can be located.Applying MTM,one can create a NCC value space of a real PCB image.The captured PCB image,with 762pixels x 612pixels,and the four template images of the resis-tors are shown in Fig.6.Every NCC value is calculated exhaustively at each pixel by the MTM approach.There are six global optima and many local optima.Every global optimum represents a pre-ferred matching of the template and the target object.The problem of locating multiple resistors can be solved when all the global peaks can be detected.

Although the Chaotic SPSO approach can track multiple peaks adaptively and concurrently,for multiple templates

matching

Fig.6.The captured PCB image and the four template resistor

images.

processes,it cannot avoid being trapped in the local optima,with-out guidance,in some situations like in other heuristic methods.In addition,revisiting a visited pixel by the particles deters the algo-rithm from searching for the optima.In order to further overcome the de?ciencies of the Chaotic SPSO based MTM method,re-initial-ization and NCC value table(Wu et al.,2009)are introduced to im-prove the searching process.Re-initialization means that when the iteration reaches a prede?ned level,all species will be reinitialized to avoid them from tracking a few optima without exploring the potential optimum.

At the same time,a NCC table has been constructed for storing the NCC value of every‘‘visited’’pixel.Once a particle reaches a pixel,a chosen NCC value will be obtained and stored in the table during the entire searching process.So,when other particles‘‘visit’’the same pixel,the NCC value can be loaded directly from the table without any calculation.The re-initialization can improve the con-vergence situation of the SPSO based MTM method whereas the NCC value table can directly speed up the searching process.

Using the Chaotic SPSO,each particle represents a position which is initialized within the2D search space and is encoded in ?oat format.The solution is represented by the rounded value of the particle location,which represents the corresponding pixel https://www.sodocs.net/doc/5b6202938.html,bining with the strategies of re-initialization and NCC value table,the?ow chart of the Chaotic SPSO based MTM is shown in Fig.7and the pseudo code of the Chaotic SPSO based MTM can be seen in Fig.8

4.Experimental studies

To test the proposed Chaotic SPSO based MTM method,a PCB image with six resistors(Fig.6),tested in previous researches(Cris-pin&Rankov,2007;Wu et al.,2009),is used in a simulation.

The acceleration strategies of re-initialization and NCC value ta-ble are adopted in the test.In this simulation,the re-initialization interval is500,which does not only guarantee the current species can be fully converged but also unleashing them to search for more potential optima.

Satisfactory results were obtained and are shown in Table3.The Chaotic SPSO based MTM algorithm parameters in the setup are: the inertia weight x=0.5,the cognitive coef?cients c1=c2=2 and the particle velocity initializes between[à4,4];the whole pro-cess becomes more stable when c s changes from30to80.The bet-ter set of parameters is Particle number of50and Species radius of 80,which has been highlighted in Table3.For simulation compar-isons,SPSO based MTM method and GA based generalized tem-plate method for solving the problem of checking multiple components on a PCB(Crispin&Rankov,2007)is introduced. The SPSO based MTM algorithm parameters in the setup are the same as the Chaotic SPSO based MTM method,and the GA param-eters are?xed as:crossover ratio0.6,mutation ratio0.05and0.1,

Table3

Test results of six resistors detection based on Chaotic SPSO based MTM.

Particle number c s Min.run time(s)Max.run time(s)Successful rate*(%)Time(mean and std.err.)Checked pixels(mean and std.err.)

503013.14172.65610036.16±20.7933050±17338

50 6.10950.12510029.66±13.3532954±9523

809.01639.57910015.71±4.3525632±6826

Chaotic

SPSO 66 6.00±0.00

N.Dong et al./Expert Systems with Applications39(2012)12501–1251112507

The searching process of Chaotic SPSO at the6500th iteration(6resistors detected).

Mean search time against the number of objects being detected and Chaotic SPSO.

maximum generation5000.The computation results are shown 4and5separately,and the better set of SPSO’s parameters Particle number of80and Species radius of80,which has highlighted in Table4.

template images for each component to be inspected,is adopted in the experiment.The generalized template is combined linearly Table 7

Experimental results based on Chaotic SPSO-MTM.Fig.15.The experimental result with 8resistors recognized and located.

are reduced by42.2%and9.6%respectively,comparing with the SPSO based approach.As a?nal,two practical applications have been used to con?rm the capability and applicability of the pro-posed method.According to this research,the power of the Chaotic SPSO has been revealed.The Chaotic SPSO based approach in image processing and vision applications is still untapped,hence our fu-ture research will aim at investigating other possible applications, such as shape recognition and segmentation. Acknowledgements

Our gratitude is extended to the research committee and the Department of Industrial and Systems Engineering of the Hong Kong Polytechnic University for support in this project(H-ZD88). This work is also supported in part by the Program for New Cen-tury Excellent Talents in Universities of China(NCET-10-0506), the Natural Science Foundation of China(61174094,60904064), the Specialized Research Fund for the Doctoral Program of Higher Education of China Under Grant20090031110029.

References

Angeline,P.J.(1998).Evolutionary optimization versus particle swarm optimization:Philosophy and performance differences.In Proceedings of the seventh annual conference on evolutionary programming(EP)VII(pp.601–610).California.

Crispin,A.J.,&Rankov,V.(2007).Automated inspection of PCB components using a genetic algorithm template-matching approach.International Journal of Advanced Manufacturing Technology,35,293–300.

Goldberg, D.E.,&Richardson,J.(1987).Genetic algorithms with sharing for multimodal function optimization.In Proceedings of the second international conference on genetic algorithms(ICGA)(pp.41–49).New Jersey.

Jiang,H.M.,Kwong,C.K.,Chen,Z.Q.,&Ysim,Y.C.(2012).Chaos particle swarm optimization and T-S fuzzy modeling approaches to constrained predictive control.Expert Systems with Applications,39(1),194–201.

Kennedy,J.,&Eberhart,R.(1995).Particle swarm optimization.In P roceedings of the ieee international conference on neural network(pp.1942–1948).Australia.

Li, B.,&Jiang,W.S.(1998).Optimizing complex functions by chaos search.

International Journal of Cybernetics and systems,29(4),409–419.Li,J.P.,Balazs,M.E.,Parks,G.T.,&Clarkson,P.J.(2002).A species conserving genetic algorithm for multimodal function optimization.Evolutionary Computation,10(3),207–234.

Liu,B.,Wang,L.,Jin,Y.H.,Tang,F.,&Huang,D.X.(2005).Improved particle swarm optimization combined with chaos.Chaos Solitons&Fractals,25,1261–1271. Li,X.D.(2004).Adaptively choosing neighborhood bests using species in a particle swarm optimizer for multimodal function optimization.Lecture Notes in Computer Science,3102,105–116.

Lu,Z.,Shieh,L.S.,&Chen,G.R.(2003).On robust control of uncertain chaotic systems:a sliding mode synthesis via chaotic optimization.Chaos Solitons& Fractals,18,819–827.

Moganti,M.,&Ercal,F.(1996).Automatic PCB inspection algorithms,a survey.

Computer Vision and Image Understanding,63(2),287–313.

Omran,M.,&Engelbrecht,A.P.(2005).Particle swarm optimization method for image clustering.International Journal of Pattern Recognition and Arti?cial Intelligence,19,297–321.

Parrott,D.,&Li,X.(2006).Locating and tracking multiple dynamic optima by a particle swarm model using speciation.IEEE Transactions on Evolutionary Computation,10(4),440–457.

Petalas,Y.G.,Antonopoulos,C.G.,Bountis,T.C.,&Vrahatis,M.N.(2009).Detecting resonances in conservative maps using evolutionary algorithms.Physics Letter A, 373,334–341.

Seul,M.,O’Gorman,L.,&Sammon,M.J.(2000).Practical algorithms references for image analysis.Description Examples and Code.Cambridge University Press. Song,Y.,Chen,Z.Q.,&Yuan,Z.Z.(2007).New chaotic PSO-based neural network predictive control for nonlinear process.IEEE Transactions on Neural Network, 18(2),595–600.

Sun,T.H.(2009).Applying particle swarm optimization algorithm to roundness measurement.Expert Systems with Applications,36,3428–3438.

Wang,D.Z.,Wu,C.H.,Ip,W.H.,Chan,C.Y.,&Wang,D.W.(2008).Fast multi-template matching using a particle swarm optimization algorithm for PCB inspection.Lecture Notes in Computer Science,4974,365–370.

Wong,K.W.,Kwok,S.H.,&Law,W.S.(2008).A fast image encryption scheme based on chaotic standard map.Physics Letter A,372,2645–2652.

Wu,C.H.,Wang,D.Z.,Ip,W.H.,Wang,D.W.,Chan,C.Y.,&Wang,H.F.(2009).A particle swarm optimization approach for components placement inspection on printed circuit boards.Journal of Intelligent Manufacturing,20(5),535–549. Xie,X.,Zang,W.,&Yang,Z.(2002).A dissipative swarm optimization.In P roceedings of the IEEE Congress on Evolutionary Computation(CEC)(pp.1456–1461)Hawaii. Zhang,H.,Shen,J.H.,Zhang,T.N.,&Li,Y.(2008).An improved chaotic particle swarm optimization and its application in investment.In Proceedings of the international symposium on computational intelligence and design(ISCID)(pp.

124–128)Wuhan.

Zhao,C.L.,Sun,X.B.,Sun,S.L.,&Jiang,T.(2011).Fault diagnosis of sensor by chaos particle swarm optimization algorithm and support vector machine.Expert Systems with Applications,38(8),9908–9912.

N.Dong et al./Expert Systems with Applications39(2012)12501–1251112511

Chaotic species based particle swarm optimization

相关文档

最新文档