Genetic Quantum Algorithm And Its Application To-Books Pdf

Genetic Quantum Algorithm and its Application to
29 Sep 2020 | 0 views | 0 downloads | 7 Pages | 569.16 KB

Share Pdf : Genetic Quantum Algorithm And Its Application To

Download and Preview : Genetic Quantum Algorithm And Its Application To

Report CopyRight/DMCA Form For : Genetic Quantum Algorithm And Its Application To



Transcription

2 1 Representation store the best solution among P t. while not termination condition do, It is possible to use a number of different representations to begin. encode the solutions onto chromosomes in evolutionary com t t t l. putation The classical representations can be broadly classi make P t by observing Q t 1 states. fied as binary numeric and symbolic 9 GQA uses a novel evaluate P t. representation that is based on the concept of qubits One. update Q t using quantum gates U t, qubit is defined with a pair of complex numbers a as store the best solution among P t. which is chzacterized by 1 and 2 And an m qubits rep GQA is a probabilistic algorithm which iS SimikU to a ge. resentation is defined as netic algorithm GQA maintains a population of qubit chro. mosomes Q t qt q qk at generation t where, 3 n is the size of population and q is a qubit chromosome. defined as, where laiI2 lfliI2 1 i 1 2 m This representation. has the advantage that it is able to represent any superposition. of states If there is for instance a three qubits system with. three pairs of amplitudes such as where m is the number of qubits i e the string length of the. qubit chromosome and j 1 2 n, In the step of initialize Q t ai and pit i 1 2 m.
of all q j 1 2 n in Q t are initialized with, It means that one qubit chromosome q it represents the. the state of the system can be represented as linear superposition of all possible statevwith the same prob. The above result means that the probabilities to represent the. state OOO IOOl IlOO and 1101 are i i i, and re where Skis the k th state represented by the binary string. spectively By consequence the three qubits system of 4 q z z zm. where zi i 1 2 m is either 0 or 1, has four states information at the same time The next step makes a set of binary solutions P t by ob. Evolutionary computing with the qubit representation has serving Q t states where P t xi xi xk at gen. a better characteristic of diversity than classical approaches eration t One binary solution xi j 1 2 n is a. since it can represent superposition of states Only one qubit binary string of the length m and is formed by selecting. chromosome such as 4 is enough to represent four states but each bit using the probability of qubit either ail2or I 12. in classical representation at least four chromosomes 000 i 1 2 m of qi Each solution xi is evaluated to give. OOl loo and 101 are needed Convergence can be some measure of its fitness The initial best solution is then. also obtained with the qubit representation As ail2 or I I2 selected and stored among the binary solutions P t. approaches to 1 or 0 the qubit chromosome converges to a In the while loop one more step update Q t is in. single state and the property of diversity disappears gradu cluded to have fitter states of the qubit chromosomes A set of. ally That is the qubit representation is able to possess the binary solutions P t is formed by observing Q t 1 states. two characteristics of exploration and exploitation simulta as with the procedure described before and each binary so. neously lution is evaluated to give the fitness value In the next step. update Q t a set of qubit chromosomes Q t is updated. 2 2 GQA by applying some appropriate quantum gates U t which is. The structure of GQA is described in the following formed by using the binary solutions P t and the stored best. solution The appropriate quantum gates can be designed in. procedure GQA compliance with practical problems Rotation gates for in. begin stance will be used for knapsack problems in the next sec. lQuantuni gates are reversible gates and can be represented as unitary. initialize Q t operators acting on the qubit basis states UtU U U t where Ut is the. make P t by observing t states hermitian adjoint of U There are several quantum gates such as NOT gate. evaluate P t Controlled NOT gate Rotation gate Hadamard gate etc 7. Authorized licensed use limited to Korea Advanced Institute of Science and Technology Downloaded on September 16 2009 at 02 14 from IEEE Xplore Restrictions apply. tion such a based on repair methods and algorithms based on decoders. cos 8 1 7 In all algorithms based on penalty functions a binary. string of the length m represents a chromosome x to the prob. lem The profit f x of each string is determined as. where 8 is a rotation angle This step makes the qubit chromo. somes converge to the fitter states The best solution among. P t is selected in the next step and if the solution is fitter f x C p i x i e n x. than the stored best solution the stored solution is changed. by the new one The binary solutions P t are discarded at where Pen x is a penalty function There are many possible. the end of the loop strategies for assigning the penalty function l 1 121 Three. It should be noted that some genetic operators can be ap types of penalties are considered such as logarithmic penalty. plied such as mutation which creates new individuals by a linear penalty and quadratic penalty. small change in a single individual and crossover which cre. ates new individuals by combining parts from two or more. P e n l x log 1 p Cclwixi C, individuals Mutation and crossover can make the probability Penz x p Cclw i z i C. of linear superposition of states change But as GQA has di 2. P e n d x p ELlw i x i C, versity caused by the qubit representation there is no need to.
use the genetic operators If the probabilities of mutation and where p is maxi l m p i w i. crossover are high the performance of GQA can be decreased In algorithms based on repair methods the profit f x of. notably each string is determined as, In GQA the population size i e the number of qubit m. chromosomes is kept the same all the time This is caused by. conservation of qubits based on quantum computing GQA. with the qubit representation can have better convergence. with diversity than conventional GAS which have fixed 0 and where x is a repaired vector of the original vector x Orig. 1information inal chromosomes are replaced with a 5 probability in the. experiment The two repair algorithms considered here dif. fer only in selection procedure which chooses an item for. 3 Experiment, removal from the knapsack, The knapsack problem a kind of combinatorial optimization. problem is used to investigate the performance of GQA The Rep1 random repair The selection procedure selects a ran. knapsack problem can be described as selecting from among dotn element from the knapsack. various items those items which are most profitable given RepfL greedy repair All items in the knapsack are sorted. that the knapsack has limited capacity The 0 1 knapsack in the decreasing order of their profit to weight ratios The. problem is described a given a set of m items and a knap selection procedure always chooses the last item for deletion. sack select a subset of the items so as to maximize the profit. A possible decoder for the knapsack problem is based on. f 4 m an integer representation Each chromosome is a vector of. C p i x i m integers the i th component of the vector is an integer in. i 1 the range from 1 to m i 1 The ordinal representation. subject to references a list L of items a vector is decoded by selecting. m appropriate item from the current list The two algorithms. based on decoders considered here differ only in the proce. i 1 dure of building a list L of items, where x XI x m zi is 0 or 1 pi is the profit of item. i zvi is the weight of item i and C is the capacity of the Decl random decoding The build procedure creates a list. knapsack L of items such that the order of items on the list corresponds. In this section some conventional GA methods are de to the order of i t e m in the input file which is random. scribed to experiment with the 0 1 knapsack problem and the Decz greedy decoding The build procedure creates a list. detailed algorithm of GQA for the knapsack problem follows L of items in the decreasing order of their profit to weight. 3 1 Conventional GA methods, 3 2 GQA for the knapsack problem. Three types of conventional algorithms are described and. tested algorithms based on penalty functions algorithms The algorithm of GQA for the knapsack problem is based. on the StruChiTe of GQA proposed and it contains a repair. Authorized licensed use limited to Korea Advanced Institute of Science and Technology Downloaded on September 16 2009 at 02 14 from IEEE Xplore Restrictions apply. algorithm The algorithm can be written as follows, procedure GQA.
begin O false I 0 1 0 1 0 1 0 1 0 1, initialize Q t. make P t by observing Q t states 0 1 true 0 0 5 1 1 fl 0. repair P t 1 0 false 0 01T 1 1 fl 0, evaluate P t 1 0 true 0 025 1 1 0 fl. store the best solution b among P t 1 1 false 0 0 0 5 1 1 0 fl. while t M A X G E N do 1 1 true 0 025 1 1 0 fl, t t t l Table 1 Lookup table of O i where f is the profit s ai i. make P t by observing Q t 1 states is the sign of Bi and bi and x i are the i th bits of the best. repair P t solution b and the binary solution x respectively. evaluate P t, update Q t, select an i th item from the knapsack. store the best solution b among P t, ifCL1wixi c, then knapsack overfilled c false.
A qubit string of the length m represents a linear superposi. while not knapsack overfilled do, tion of solutions to the problem as in 6 The length of a qubit. string is the same as the number of items The i th item can be. select a j th item from the knapsack, selected for the knapsack with probability I 3ilz or 1 lail. Thus a binary string of the length m is formed from the qubit. string For every bit in the binary string we generate a ran. if CL1wixi C, then knapsack overfilled t Vue, dom number T from the range 0 1 if r laiI2 we set the. bit of the binary string The binary string xf j 1 2 n. of P t represents a j th solution to the problem For nota. tional simplicity x is used instead of xf in the following The. i th item is selected for the knapsack iff xi 1 where x i is. the i th bit of x The binary string x is determined as follows The profit of a binary solution x is evaluated by pixi. and it is used to find the best solution b after the update of qi. j 1 2 n A qubit chromosome sj is updated by using, procedure make x. the rotation gate U 0 of 7 in this algorithm The i th qubit. value ai P i is updated as, while i m do, if randomlo 1 Iai12 In this knapsack problem 0 is given as s aipi A The.
thenzi t 1 parameters used are shown in Table 1 For example if the. else x i t 0 condition f x 2 f b is satisfied and x i and bi are 1and. end 0 respectively we can set the value of At as 0 0 2 5 and. end s aipi as 1 1 or 0 according to the condition of a so. as to increase the probability of the state 11 The value of AOi. The repair algorithm of GQA for the knapsack problem is has an effect on the speed of convergence but if it is too big. implemented as follows the solutions may diverge or have a premature convergence to. a local optimum The sign s a i p i determines the direction. procedure repair x of convergence to a global optimum The lookup table can be. begin used as a strategy for convergence This update procedure. knapsack overfilled t false can be described as follows. ifCE1wixi C, then knapsack overfilled t true procedure update 9. while knapsack overfilled do begin, begin i t 0, Authorized licensed use limited to Korea Advanced Institute of Science and Technology Downloaded on September 16 2009 at 02 14 from IEEE Xplore Restrictions apply. ll of CGAs GQAs, items Pen1 Pen2 Pen3 Repl Rep2 Decl Dec2 P2 R1 G Q A 1 GQA 10. b 557 7 581 4 566 0 561 1 560 2 514 7 511 0 582 2 597 5 612 5. 100 profits m 545 4 569 7 556 1 546 5 546 3 503 9 500 0 571 1 583 7 603 9. w 535 1 562 6 551 1 537 3 536 6 496 3 493 3 562 3 562 5 592 7. t sec run 1 329 1 333 1 323 1 142 1 151 3 510 10 51 1 360 0 054 0 382. b 1391 9 1444 9 1480 3, 250 profits m 1382 1 1412 4 1467 1. W 1364 8 1385 8 1443 8, t sec run 3 292 0 141 1 380.
b 2744 2 2824 1 2860 0, 250 profits m 2720 8 2771 5 2841 3. W 2699 2 2744 3 2812 5, t sec run 6 532 0 324 3 994. while i m do, i t i l one run A Pentium III 500MHz was used running Visual. determine Bi with the lookup table C 6 0, obtain ai P f as Table 2 shows the experimental results of the knapsack. problems with 100 250 and 500 items In the case of 100. ai q e ai items GQA yielded superior results as compared to all the. other CGAs The CGA designed by using a linear penalty. q q function and random repair algorithm outperformed all other. CGAs but is behind GQA 1 as well as GQA 10 in perfor. The update procedure can be implemented in various meth mance The results show that GQA performs well in spite. ods with appropriate quantum gates It depends on a given of small size of population Judging from the results GQA. problem can search solutions near the optimum within a short time. as compared to CGAs In the cases of 250 and 500 items the. CGA that outperforms all the other CGAs was tested for com. 4 Results parison purpose with GQA The experimental results again. demonstrate the superiority of GQA, In all experiments strongly correlated sets of data were con.
Figure 1 shows the progress of the mean of best prof. its and the mean of average profits of population found by. wi uniformly random l 10 GQA l GQA lo and CGA over 25 runs for 100 250 and. pi Wi 5 500 items GQA performs better than CGA in terms of con. vergence rate and final results In the beginning of the plot. Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem 0 7803 6375 2 00 10 00 02000 IEEE 1354 Kuk Hyun Han Dept of Electrical Engineering KAIST 373 1 Kusong dong Yusong gu Taejon 305 701 Republic of Korea kh han 9 vivaldi kais t ac kr Abstract This paper proposes a novel evolutionary computing method called a genetic quantum algorithm GQA GQA is

Related Books

The process approach in ISO 9001

The process approach in ISO 9001

process approach can facilitate the implementation of any management system enhanced customer satisfaction by meeting customer requirements enhanced confidence in the organization The practical steps in using a process approach in ISO 9001 2015 are explained below in Appendix A

WARNING Serviceinfo MC

WARNING Serviceinfo MC

K6 June 2005 ENTK JR50 300 TAKATSUKA HAMAMATSU JAPAN Printed in Taiwan OWNER S MANUAL This owner s manual contains important safety information Please read it carefully WARNING Failure to follow these safety precautions may increase your risk of injury Wear a helmet eye protec tion and bright protective clothing Off road use only do not use on public roads or high ways

5 2 Programmable Thermostat Honeywell

5 2 Programmable Thermostat Honeywell

malfunctions Honeywell shall repair or replace it at Honeywell s option If the product is defective i return it with a bill of sale or other dated proof of purchase to the plac e from which you purchased it or ii call Honeywell Customer Care at 1 800 468 1502 Customer Care will make the determination whether the product should be returned to the foll owing address Honeywell

NE R ANG E Specialising in under body service parts

NE R ANG E Specialising in under body service parts

E Specialising in under body service parts Driveshafts joints and boots to suit most vehicles Backed by a 1 year 50 000km warranty G100 ALL 6 87 88 24 19 46 31013 33 1500 55 3610 DSA835 M DSA836 M 33 1500 55 3610 DSA837 A DSA838 A ALL 1 89 6 93 24 19 54 31016 33 1500 55 3610 DSA769 A DSA768 A 33 1500 55 3610 DSA763 M DSA762 M 3 OF 29 COPYRIGHT RESERVED EQUIPE AUTOMOTIVE

American Literature Summer Reading List Summer 2013

American Literature Summer Reading List Summer 2013

American Literature Summer Reading List Summer 2013 Belmont High School English Department The following list was complied from the recommendations of the Belmont High School English department and contains some of the best known works of American literature Each book addresses the American Dream and or American identities All entering 11th graders must read at least one book from the list

79 Short Essays on Design

79 Short Essays on Design

Rob Roy Kelly s Old Weird America My Phone Call to Arnold Newman Howard Roark Lives The Real and the Fake Ten Footnotes to a Manifesto The New York Times Apocalypse Now Page A1 Graphic Design and the New Certainties Mark Lombardi and the Ecstasy of Conspiracy George Kennan and the Cold War Between Form and Content Errol Morris Blows Up Spreadsheet Thousands Killed Catharsis Salesmanship

Welcome to the Weird West Amazon S3

Welcome to the Weird West Amazon S3

America apart has shaped our country and indeed our world more than any other single event California had long been a land of dreams Gold was discovered there in 49 and the tales of those who had become millionaires overnight were the stuff of legend The migration of hundreds of thousands of settlers looking to partake in this miracle was what formed the early history of the Old

reinventing project management shenhar hbsp

reinventing project management shenhar hbsp

A HARVARD BUSINESS SCHOOL PRESS BOOK SUMMARY The Diamond Framework can help you map your project s novelty technology complexity and pace and to identify and manage risk Fulfilling customers needs is a more important project requirement than meeting the deadline or budget If you can imagine how the project will look to someone in the future you will see more

HPM252 DAILY CLASS READING ASSIGNMENTS Harvard University

HPM252 DAILY CLASS READING ASSIGNMENTS Harvard University

Page 1 of 6 HPM252 DAILY CLASS READING ASSIGNMENTS Class 1 March 22 Thinking Strategically Preparing to Negotiate Class 2 March 24 Distributive Bargaining Claiming Value

A Problem Solving Approach to Projects at Harvard

A Problem Solving Approach to Projects at Harvard

A Problem Solving Approach to Designing and Implementing a Strategy to Improve Performance 3 Table 1 provides an example of a root cause analysis technique called the 5 Whys The method is widely used in various continuous improvement processes 4 Your team should use your answers to the earlier questions about the problem and its symptoms as a way to get started

Philip Astley and the Legacy of Modern Circus

Philip Astley and the Legacy of Modern Circus

circus history and travelling fairs and entertainments Her publications include The Electric Edwardians the Films of Mitchell and Kenyon Pleasurelands and four monographs on Blackpool including Blackpool Tower She has appeared in over 50 radio and television programmes co produced Circus Comes to Town for the BBC and the Show of Shows a recent 70 minute archival documentary which