The Wolf Colony Algorithm and Its Application

附录I 英文翻译第一部分英文原文文章来源：书名：《自然赋予灵感的元启发示算法》第二、三章出版社：英国Luniver出版社出版日期：2008Chapter 2Genetic Algorithms2.1 IntroductionThe genetic algorithm (GA), developed by John Holland and his collaborators in the 1960s and 1970s, is a model or abstraction of biolo gical evolution based on Charles Darwin’s theory of natural selection. Holland was the first to use the crossover and recombination, mutation, and selection in the study of adaptive and artificial systems. These genetic operators form the essential part of the genetic algorithm as a problem-solving strategy. Since then, many variants of genetic algorithms have been developed and applied to a wide range of optimization problems, from graph colouring to pattern recognition, from discrete systems (such as the travelling salesman problem) to continuous systems (e.g., the efficient design of airfoil in aerospace engineering), and from financial market to multiobjective engineering optimization.There are many advantages of genetic algorithms over traditional optimization algorithms, and two most noticeable advantages are: the ability of dealing with complex problems and parallelism. Genetic algorithms can deal with various types of optimization whether the objective (fitness) functionis stationary or non-stationary (change with time), linear or nonlinear, continuous or discontinuous, or with random noise. As multiple offsprings in a population act like independent agents, the population (or any subgroup) can explore the search space in many directions simultaneously. This feature makes it ideal to parallelize the algorithms for implementation. Different parameters and even different groups of strings can be manipulated at the same time.However, genetic algorithms also have some disadvantages.The formulation of fitness function, the usage of population size, the choice of the important parameters such as the rate of mutation and crossover, and the selection criteria criterion of new population should be carefully carried out. Any inappropriate choice will make it difficult for the algorithm to converge, or it simply produces meaningless results.2.2 Genetic Algorithms2.2.1 Basic ProcedureThe essence of genetic algorithms involves the encoding of an optimization function as arrays of bits or character strings to represent the chromosomes, the manipulation operations of strings by genetic operators, and the selection according to their fitness in the aim to find a solution to the problem concerned. This is often done by the following procedure:1) encoding of the objectives or optimization functions; 2) defining a fitness function or selection criterion; 3) creating a population of individuals; 4) evolution cycle or iterations by evaluating the fitness of allthe individuals in the population,creating a new population by performing crossover, and mutation,fitness-proportionate reproduction etc, and replacing the old population and iterating again using the new population;5) decoding the results to obtain the solution to the problem. These steps can schematically be represented as the pseudo code of genetic algorithms shown in Fig. 2.1.One iteration of creating a new population is called a generation. The fixed-length character strings are used in most of genetic algorithms during each generation although there is substantial research on the variable-length strings and coding structures.The coding of the objective function is usually in the form of binary arrays or real-valued arrays in the adaptive genetic algorithms. For simplicity, we use binary strings for encoding and decoding. The genetic operators include crossover,mutation, and selection from the population.The crossover of two parent strings is the main operator with a higher probability and is carried out by swapping one segment of one chromosome with the corresponding segment on another chromosome at a random position (see Fig.2.2).The crossover carried out in this way is a single-point crossover. Crossover at multiple points is also used in many genetic algorithms to increase the efficiency of the algorithms.The mutation operation is achieved by flopping the randomly selected bits (see Fig. 2.3), and the mutation probability is usually small. The selection of anindividual in a population is carried out by the evaluation of its fitness, and it can remain in the new generation if a certain threshold of the fitness is reached or the reproduction of a population is fitness-proportionate. That is to say, the individuals with higher fitness are more likely to reproduce.2.2.2 Choice of ParametersAn important issue is the formulation or choice of an appropriate fitness function that determines the selection criterion in a particular problem. For the minimization of a function using genetic algorithms, one simple way of constructing a fitness function is to use the simplest form F = A−y with A being a large constant (though A = 0 will do) and y = f(x), thus the objective is to maximize the fitness function and subsequently minimize the objective function f(x). However, there are many different ways of defining a fitness function.For example, we can use the individual fitness assignment relative to the whole populationwhere is the phenotypic value of individual i, and N is the population size. The appropriateform of the fitness function will make sure that the solutions with higher fitness should be selected efficiently. Poor fitness function may result in incorrect or meaningless solutions.Another important issue is the choice of various parameters.The crossover probability is usually very high, typically in the range of 0.7~1.0. On the other hand, the mutation probability is usually small (usually 0.001 _ 0.05). If is too small, then the crossover occurs sparsely, which is not efficient for evolution. If the mutation probability is too high, the solutions could still ‘jump around’ even if the optimal solution is approaching.The selection criterion is also important. How to select the current population so that the best individuals with higher fitness should be preserved and passed onto the next generation. That is often carried out in association with certain elitism. The basic elitism is to select the most fit individual (in each generation) which will be carried over to the new generation without being modified by genetic operators. This ensures that the best solution is achieved more quickly.Other issues include the multiple sites for mutation and the population size. The mutation at a single site is not very efficient, mutation at multiple sites will increase the evolution efficiency. However, too many mutants will make it difficult for the system to converge or even make the system go astray to the wrong solutions. In reality, if the mutation is too high under high selection pressure, then the whole population might go extinct.In addition, the choice of the right population size is also very important. If the population size is too small, there is not enough evolution going on, and there is a risk for the whole population to go extinct. In the real world, a species with a small population, ecological theory suggests that there is a real danger of extinction for such species. Even the system carries on, there is still a danger of premature convergence. In a small population, if a significantly more fit individual appears too early, it may reproduces enough offsprings so that they overwhelm the whole (small) population. This will eventually drive the system to a local optimum (not the global optimum). On the other hand, if the population is too large, more evaluations of the objectivefunction are needed, which will require extensive computing time.Furthermore, more complex and adaptive genetic algorithms are under active research and the literature is vast about these topics.2.3 ImplementationUsing the basic procedure described in the above section, we can implement the genetic algorithms in any programming language. For simplicity of demonstrating how it works, we have implemented a function optimization using a simple GA in both Matlab and Octave.For the generalized De Jong’s test function where is a positive integer andr > 0 is the half length of the domain. This function has a minimum of at . For the values of , r = 100 and n = 5 as well as a population size of 40 16-bit strings, the variations of the objective function during a typical run are shown in Fig. 2.4. Any two runs will give slightly different results dueto the stochastic nature of genetic algorithms, but better estimates are obtained as the number of generations increases.For the well-known Easom functionit has a global maximum at (see Fig. 2.5). Now we can use the following Matlab/Octave to find its global maximum. In our implementation, we have used fixedlength 16-bit strings. The probabilities of crossover and mutation are respectivelyAs it is a maximization problem, we can use the simplest fitness function F = f(x).The outputs from a typical run are shown in Fig. 2.6 where the top figure shows the variations of the best estimates as they approach while the lower figure shows the variations of the fitness function.% Genetic Algorithm (Simple Demo) Matlab/Octave Program% Written by X S Yang (Cambridge University)% Usage: gasimple or gasimple(‘x*exp(-x)’);function [bestsol, bestfun,count]=gasimple(funstr)global solnew sol pop popnew fitness fitold f range;if nargin<1,% Easom Function with fmax=1 at x=pifunstr=‘-cos(x)*exp(-(x-3.1415926)^2)’;endrange=[-10 10]; % Range/Domain% Converting to an inline functionf=vectorize(inline(funstr));% Generating the initil populationrand(‘state’,0’); % Reset the random generatorpopsize=20; % Population sizeMaxGen=100; % Max number of generationscount=0; % counternsite=2; % number of mutation sitespc=0.95; % Crossover probabilitypm=0.05; % Mutation probabilitynsbit=16; % String length (bits)% Generating initial populationpopnew=init_gen(popsize,nsbit);fitness=zeros(1,popsize); % fitness array% Display the shape of the functionx=range(1):0.1:range(2); plot(x,f(x));% Initialize solution <- initial populationfor i=1:popsize,solnew(i)=bintodec(popnew(i,:));end% Start the evolution loopfor i=1:MaxGen,% Record as the historyfitold=fitness; pop=popnew; sol=solnew;for j=1:popsize,% Crossover pairii=floor(popsize*rand)+1; jj=floor(popsize*rand)+1;% Cross overif pc>rand,[popnew(ii,:),popnew(jj,:)]=...crossover(pop(ii,:),pop(jj,:));% Evaluate the new pairscount=count+2;evolve(ii); evolve(jj);end% Mutation at n sitesif pm>rand,kk=floor(popsize*rand)+1; count=count+1;popnew(kk,:)=mutate(pop(kk,:),nsite);evolve(kk);endend % end for j% Record the current bestbestfun(i)=max(fitness);bestsol(i)=mean(sol(bestfun(i)==fitness));end% Display resultssubplot(2,1,1); plot(bestsol); title(‘Best estimates’); subplot(2,1,2); plot(bestfun); title(‘Fitness’);% ------------- All sub functions ----------% generation of initial populationfunction pop=init_gen(np,nsbit)% String length=nsbit+1 with pop(:,1) for the Signpop=rand(np,nsbit+1)>0.5;% Evolving the new generationfunction evolve(j)global solnew popnew fitness fitold pop sol f;solnew(j)=bintodec(popnew(j,:));fitness(j)=f(solnew(j));if fitness(j)>fitold(j),pop(j,:)=popnew(j,:);sol(j)=solnew(j);end% Convert a binary string into a decimal numberfunction [dec]=bintodec(bin)global range;% Length of the string without signnn=length(bin)-1;num=bin(2:end); % get the binary% Sign=+1 if bin(1)=0; Sign=-1 if bin(1)=1.Sign=1-2*bin(1);dec=0;% floating point.decimal place in the binarydp=floor(log2(max(abs(range))));for i=1:nn,dec=dec+num(i)*2^(dp-i);enddec=dec*Sign;% Crossover operatorfunction [c,d]=crossover(a,b)nn=length(a)-1;% generating random crossover pointcpoint=floor(nn*rand)+1;c=[a(1:cpoint) b(cpoint+1:end)];d=[b(1:cpoint) a(cpoint+1:end)];% Mutatation operatorfunction anew=mutate(a,nsite)nn=length(a); anew=a;for i=1:nsite,j=floor(rand*nn)+1;anew(j)=mod(a(j)+1,2);endThe above Matlab program can easily be extended to higher dimensions. In fact, there is no need to do any programming (if you prefer) because there are many software packages (either freeware or commercial) about genetic algorithms. For example, Matlab itself has an extra optimization toolbox.Biology-inspired algorithms have many advantages over traditional optimization methods such as the steepest descent and hill-climbing and calculus-based techniques due to the parallelism and the ability of locating the very good approximate solutions in extremely very large search spaces.Furthermore, more powerful new generation algorithms can be formulated by combiningexisting and new evolutionary algorithms with classical optimization methods.Chapter 3Ant AlgorithmsFrom the discussion of genetic algorithms, we know that we can improve the search efficiency by using randomness which will also increase the diversity of the solutions so as to avoid being trapped in local optima. The selection of the best individuals is also equivalent to use memory. In fact, there are other forms of selection such as using chemical messenger (pheromone) which is commonly used by ants, honey bees, and many other insects. In this chapter, we will discuss the nature-inspired ant colony optimization (ACO), which is a metaheuristic method.3.1 Behaviour of AntsAnts are social insects in habit and they live together in organized colonies whose population size can range from about 2 to 25 millions. When foraging, a swarm of ants or mobile agents interact or communicate in their local environment. Each ant can lay scent chemicals or pheromone so as to communicate with others, and each ant is also able to follow the route marked with pheromone laid by other ants. When ants find a food source, they will mark it with pheromone and also mark the trails to and from it. From the initial random foraging route, the pheromone concentration varies and the ants follow the route with higher pheromone concentration, and the pheromone is enhanced by the increasing number of ants. As more and more ants follow the same route, it becomes the favoured path. Thus, some favourite routes (often the shortest or more efficient) emerge. This is actually a positive feedback mechanism.Emerging behaviour exists in an ant colony and such emergence arises from simple interactions among individual ants. Individual ants act according to simple and local information (such as pheromone concentration) to carry out their activities. Although there is no master ant overseeing the entire colony and broadcasting instructions to the individual ants, organized behaviour still emerges automatically. Therefore, such emergent behaviour is similar to other self-organized phenomena which occur in many processes in nature such as the pattern formation in animal skins (tiger and zebra skins).The foraging pattern of some ant species (such as the army ants) can show extraordinary regularity. Army ants search for food along some regular routes with an angle of about apart. We do not know how they manage to follow such regularity, but studies show that they could move in an area and build a bivouac and start foraging. On the first day, they forage in a random direction, say, the north and travel a few hundred meters, then branch to cover a large area. The next day, they will choose a different direction, which is about from the direction on the previous day and cover a large area. On the following day, they again choose a different direction about from the second day’s direction. In this way, they cover the whole area over about 2 weeks and they move out to a different location to build a bivouac and forage again.The interesting thing is that they do not use the angle of (this would mean that on the fourth day, they will search on the empty area already foraged on the first day). The beauty of this angle is that it leaves an angle of about from the direction on the first day. This means they cover the whole circle in 14 days without repeating (or covering a previously-foraged area). This is an amazing phenomenon.3.2 Ant Colony OptimizationBased on these characteristics of ant behaviour, scientists have developed a number ofpowerful ant colony algorithms with important progress made in recent years. Marco Dorigo pioneered the research in this area in 1992. In fact, we only use some of the nature or the behaviour of ants and add some new characteristics, we can devise a class of new algorithms.The basic steps of the ant colony optimization (ACO) can be summarized as the pseudo code shown in Fig. 3.1.Two important issues here are: the probability of choosing a route, and the evaporation rate of pheromone. There are a few ways of solving these problems although it is still an area of active research. Here we introduce the current best method. For a network routing problem, the probability of ants at a particular node to choose the route from node to node is given bywhere and are the influence parameters, and their typical values are .is the pheromone concentration on the route between and , and the desirability ofthe same route. Some knowledge about the route such as the distance is often used so that ,which implies that shorter routes will be selected due to their shorter travelling time, and thus the pheromone concentrations on these routes are higher.This probability formula reflects the fact that ants would normally follow the paths with higher pheromone concentrations. In the simpler case when , the probability of choosing a path by ants is proportional to the pheromone concentration on the path. The denominator normalizes the probability so that it is in the range between 0 and 1.The pheromone concentration can change with time due to the evaporation of pheromone. Furthermore, the advantage of pheromone evaporation is that the system could avoid being trapped in local optima. If there is no evaporation, then the path randomly chosen by the first ants will become the preferred path as the attraction of other ants by their pheromone. For a constant rate of pheromone decay or evaporation, the pheromone concentration usually varies with time exponentiallywhere is the initial concentration of pheromone and t is time. If , then we have . For the unitary time increment , the evaporation can beapproximated by . Therefore, we have the simplified pheromone update formula:where is the rate of pheromone evaporation. The increment is the amount of pheromone deposited at time t along route to when an ant travels a distance . Usually . If there are no ants on a route, then the pheromone deposit is zero.There are other variations to these basic procedures. A possible acceleration scheme is to use some bounds of the pheromone concentration and only the ants with the current global best solution(s) are allowed to deposit pheromone. In addition, certain ranking of solution fitness can also be used. These are hot topics of current research.3.3 Double Bridge ProblemA standard test problem for ant colony optimization is the simplest double bridge problem with two branches (see Fig. 3.2) where route (2) is shorter than route (1). The angles of these two routes are equal at both point A and pointB so that the ants have equal chance (or 50-50 probability) of choosing each route randomly at the initial stage at point A.Initially, fifty percent of the ants would go along the longer route (1) and the pheromone evaporates at a constant rate, but the pheromone concentration will become smaller as route (1) is longer and thus takes more time to travel through. Conversely, the pheromone concentration on the shorter route will increase steadily. After some iterations, almost all the ants will move along the shorter route. Figure 3.3 shows the initial snapshot of 10 ants (5 on each route initially) and the snapshot after 5 iterations (or equivalent to 50 ants have moved along this section). Well, there are 11 ants, and one has not decided which route to follow as it just comes near to the entrance.Almost all the ants (well, about 90% in this case) move along the shorter route.Here we only use two routes at the node, it is straightforward to extend it to the multiple routes at a node. It is expected that only the shortest route will be chosen ultimately. As any complex network system is always made of individual nodes, this algorithms can be extended to solve complex routing problems reasonably efficiently. In fact, the ant colony algorithms have been successfully applied to the Internet routing problem, the travelling salesman problem, combinatorial optimization problems, and other NP-hard problems.3.4 Virtual Ant AlgorithmAs we know that ant colony optimization has successfully solved NP-hard problems such asthe travelling salesman problem, it can also be extended to solve the standard optimization problems of multimodal functions. The only problem now is to figure out how the ants will move on an n-dimensional hyper-surface. For simplicity, we will discuss the 2-D case which can easily be extended to higher dimensions. On a 2D landscape, ants can move in any direction or , but this will cause some problems. How to update the pheromone at a particular point as there are infinite number of points. One solution is to track the history of each ant moves and record the locations consecutively, and the other approach is to use a moving neighbourhood or window. The ants ‘smell’ the pheromone concentration of their neighbourhood at any particular location.In addition, we can limit the number of directions the ants can move by quantizing the directions. For example, ants are only allowed to move left and right, and up and down (only 4 directions). We will use this quantized approach here, which will make the implementation much simpler. Furthermore, the objective function or landscape can be encoded into virtual food so that ants will move to the best locations where the best food sources are. This will make the search process even more simpler. This simplified algorithm is called Virtual Ant Algorithm (VAA) developed by Xin-She Yang and his colleagues in 2006, which has been successfully applied to topological optimization problems in engineering.The following Keane function with multiple peaks is a standard test functionThis function without any constraint is symmetric and has two highest peaks at (0, 1.39325) and (1.39325, 0). To make the problem harder, it is usually optimized under two constraints:This makes the optimization difficult because it is now nearly symmetric about x = y and the peaks occur in pairs where one is higher than the other. In addition, the true maximum is, which is defined by a constraint boundary.Figure 3.4 shows the surface variations of the multi-peaked function. If we use 50 roaming ants and let them move around for 25 iterations, then the pheromone concentrations (also equivalent to the paths of ants) are displayed in Fig. 3.4. We can see that the highest pheromoneconcentration within the constraint boundary corresponds to the optimal solution.It is worth pointing out that ant colony algorithms are the right tool for combinatorial and discrete optimization. They have the advantages over other stochastic algorithms such as genetic algorithms and simulated annealing in dealing with dynamical network routing problems.For continuous decision variables, its performance is still under active research. For the present example, it took about 1500 evaluations of the objective function so as to find the global optima. This is not as efficient as other metaheuristic methods, especially comparing with particle swarm optimization. This is partly because the handling of the pheromone takes time. Is it possible to eliminate the pheromone and just use the roaming ants? The answer is yes. Particle swarm optimization is just the right kind of algorithm for such further modifications which will be discussed later in detail.第二部分中文翻译第二章遗传算法2.1 引言遗传算法是由John Holland和他的同事于二十世纪六七十年代提出的基于查尔斯·达尔文的自然选择学说而发展的一种生物进化的抽象模型。

英文算法比赛作文范文I love algorithm competitions. The thrill of solving complex problems under time pressure is just so exciting.It's like a mental workout that keeps my brain sharp and focused.The best part about algorithm competitions is the sense of accomplishment when you finally crack a tough problem.It's like a victory dance in your head, and it feels amazing. Plus, it's a great way to showcase your problem-solving skills and creativity.When I first started participating in algorithm competitions, I was intimidated by the level of competition. But as I kept practicing and learning from others, Irealized that everyone starts somewhere. It's all about the journey of improvement and growth.The community aspect of algorithm competitions is also something I really enjoy. It's awesome to meet like-mindedpeople who share the same passion for problem-solving. We exchange tips, tricks, and strategies, and it's a great way to learn from each other.The adrenaline rush during the competition is unbeatable. The clock is ticking, and you're frantically trying to come up with the most efficient solution. It's like a race against time, and the feeling of solving a problem just before the buzzer goes off is indescribable.Overall, algorithm competitions have been an incredibly rewarding experience for me. It's not just about the competition itself, but the journey of self-improvement, the friendships made, and the sheer joy of problem-solving.I can't wait for the next competition!。

Linux学习篇（七）：Linux驱动开发书籍推荐书籍表格，同序号的可能是同⼀书的中英两版，序号越⼩推荐强度越⾼：0--understanding-the-linux-kernel1--鸟哥的Linux私房菜-基础学习篇(第四版)1--深⼊Linux内核架构Wolfgang Mauerer1--Linux Kernel Development, 3rd Edition A thorough guide to the design and implementation of the Linux kernel by Robert Love1--Professional Linux Kernel Architecture by Wolfgang Mauerer2----精通LINUX设备驱动开发2--Essential Linux Device Drivers by Sreekrishnan Venkateswaran3--Advanced Programming in the UNIX Environment by W. Richard Stevens, Stephen A. Rago3--[UNIX环境⾼级编程_第⼆版]3--UNIX环境⾼级编程（中⽂第三版）4--Linux Device Driver Development Cookbook Develop custom drivers for your embedded Linux applications by Rodolfo Giometti5--Linux设备驱动开发详解：基于最新的Linux 4.0内核6--Linux Device Drivers, 3rd Edition by Jonathan Corbet, Alessandro Rubini, Greg Kroah-Hartman6--Linux For Beginners The Ultimate Guide To The Linux Operating System Linux by Vardy Adam.6--the-art-of-debugging-with-gdb-ddd-and-eclipse7--Managing Projects with GNU Make, 3rd Edition by Mecklenburg Robert编程之美 by 《编程之美》⼩组编程珠玑第2版 by Jon Bentley编码隐匿在计算机软硬件背后的语⾔ by [美] Charles Petzold计算机⽹络：⾃顶向下⽅法（第6版） by Keith W.Ross,James F.Kurose计算机组成与设计：硬件软件接⼝ by David A. Patterson, John L. Hennessy剑指Offer 名企⾯试官精讲典型编程题 by 何海涛⼈⽉神话（32周年中⽂纪念版）深⼊理解机器学习：从原理到算法从原理到算法 by Shai Shalev Shwartz Shai Ben David深⼊理解云计算基本原理和应⽤程序编程技术 by Rajkumar Buyya Christian Vecchiola,S.T算法导论（原书第3版）_中⽂ by [美] Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein算法（第四版）中⽂版图灵程序设计丛书 Algorithms (Incomplete) by 美 Robert Sedgewick 美 Kevin Wayne译谢路云算法图解 by [美] Aditya Bhargava我的第⼀本算法书 by ⽯⽥保辉宫崎修⼀Advanced Linux programming by Mark Mitchell JeffrAlberto Liberal De Los Ríos - Linux Driver Development for Embedded Processors - Second Edition_ Learn to develop Linux embedded drivers with kernel 4.9 LTS-Independently published (2018)Beginning Linux programming by Neil Matthew RichaDC1--第⼀本Docker书修订版 by [澳] 詹姆斯·特恩布尔James TurnbullDC1--The Docker Book by James TurnbullHow Linux Works What Every Superuser Should Know by Brian WardJohn Madieu - Linux Device Drivers Development_ Develop customized drivers for embedded Linux-Packt Publishing (2017)Linux Basics for Hackers Getting Started with Networking, Scripting, and Security in Kali by OccupyTheWebLinux Kernel Module Programming Guide by Peter Jay Salzman, Michael Burian, Ori PomerantzOS0--深⼊理解计算机系统（原书第3版）by Randal E.Bryant David OHallaronOS1--现代操作系统 Modern Operation Systems by Andrew S. Tanenbaum Array ArrayOS1--Modern Operating Systems by Andrew S. Tanenbaum, Herbert BosTCPIP详解卷1：协议（原书第2版） by 凯⽂.R.福尔,W.理查德.史蒂⽂斯UNIX and Linux System Administration Handbook by Evi Nemeth et al.。

ASYMPTOTIC QUANTUM SEARCH AND A QUANTUM ALGORITHM FOR CALCULATION OF A LOWER BOUND OF THE PROBABILITY OF FINDING A DIOPHANTINE EQUATIONTHAT ACCEPTS INTEGER SOLUTIONSR. V. Ramos and J. L. de Oliveirarubens@deti.ufc.br jluzeilton@deti.ufc.brDepartment of Teleinformatic Engineering, Federal University of CearaCampus do Pici, C. P. 6007, 60455-740, Fortaleza, Brazil.Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed and all of them use the quantum search algorithm as a subroutine and several intermediate measurements are realized. In this work, it is proposed a new quantum algorithm for finding the minimum of a function in which quantum search is not used as a subroutine and only one measurement is needed. This is also named asymptotic quantum search. As an example, we propose a quantum algorithm based on asymptotic quantum search and quantum counting able to calculate a lower bound of the probability of finding a Diophantine equation with integer solution.Keywords:Quantum algorithms, quantum search, optimization, Diophantine equations.1. IntroductionThe Grover’s quantum search algorithm is an important result in quantum computation that proves that quantum superposition can speed-up the task of finding a specific value within an unordered database. The quantum search is proved to use O(N1/2) operations of the oracle (in comparison with the O(N) operations of the best classical algorithm), indicating a quadratic speed-up [1-3]. Several mathematical problems can be modeled as a search, like the problem of finding the minimum (or the maximum) of a function. Thus, some algorithms for finding the minimum or maximum using quantum search have been proposed [4,5], using the generalization of the quantum search proposed in [6] as a subroutine that is called several times. Every time the quantum search is called, at the end a measurement is realized. The number of measurements in the algorithm proposed in [4] is (log2N), where N is the number of elements in the database [7]. Aiming to reduce the number of measurements, Kowada at al [7] proposed a new quantum algorithm for finding the minimum of a function that realizes O(log N) measurements. Here, we go beyond, proposing a quantum algorithm for finding the minimum that realizes only one measurement, at the final of the algorithm. Furthermore, conversely the already proposed quantum algorithms for finding the minimum, the quantum search in the proposed algorithm is not used as a subroutine, indeed it is a part of the algorithm as any other quantum gate. In this work, as an example, we apply asymptotic quantum search together with quantum counting algorithm [3,8] in order to create a quantum algorithm able to calculate a lower bound of the probability of finding a Diophantine equation that accepts integer solutions. We are going to call this number by D.(1)(2) (3)2. Quantum algorithm for finding the minimum of a functionThe circuit for the proposed quantum algorithm is shown in Fig. 1.Fig. 1- Circuit for asymptotic quantum search.In Fig. 1, U f is the quantum gate that implements the function f , U f x 0 = x f (x ) , the gate QBSC is a quantum bit string comparator [9], QBSC x y 0 = x y b , where b =0 if x >y and b =1 if x y . At last, the oracle in the amplitude amplification recognizes if the quantum registers 4 and 5 are in the total state 0 N 0 . In order to understand the quantum circuit in Fig. 1, we firstly show the operation of the quantum circuit U , following the states in the marked positions, as shown below:1152432151452243331451452233000000000000NNNx xNN NNNx f x x xy Nx f x xy x y c xc U x Hc xf x c xf x yc x f x f y(4.a)(4.b)(5)(6.a)41451452323, ,415243 212431101 N x y x yf x f y f x f y n x x jj xj f x f y n x x jj j xf x yf y f x yf y c x f x f y c x f x f y50xf x f y.In (1)-(4.b), N is the number of qubits, hence, there are 2N elements in the database. In (4.b), 1 n (x ) 2N is the number of elements that obey f (x ) f (y ) for a given x and all y ’s. Thus, the better the solution the larger is the value of n (x ). At last, y i can assume any y value.min 515243 215243 16min min 101 00Nn x N x j x j f x f y n x N x j xj f x f y x c x f x c x f x c x f xminmin 1522443321423 10001 0Nn x N N N N x j xj x x f x f y n x N Nx kxk x x f x f y c x fx y c xf x H y5(6.b)(7)(8)min minmin 6min min 115224343 154231 021421002001001N j NNNN NNx x xx x n x NN Nx j x j x x H y f x f y n x N x kk c x f x c n x xf x c x y c x f x H ymin53 00N x x x f x f y.Finallymin 71515243243 15423 1 0214210000200000000N N j NN NN NNNx x xxf x f y n xNNNx j xj x x H y f x f y NN x k k U c xc n x x c x y c x y53 01Nn x N xf x f yThe worse the solution the lower is the value of n (x ) and the faster is the decay. Now, using k -times the gate U together with the multi-controlled CNOTs, the quantum state just before the quantum amplification is:min 15243 1154231 1 021142120000200020N j N k N N N Nx x f x f y n x k r N N NN x j r x j x x H y f x f y n r N N Nx k k c n x x c n x x H y c n x x H y31 501x k N r x f x f y(9)At the amplitude amplification, the oracle recognizes the state 0 N 0 in the fourth and fifth quantum registers. Therefore, only the first term in (8) will have their amplitudes amplified. Looking closer the first term in (8), one sees that the amplitude of the searched answer is min x c , since n (x )=2N for x =x min . The second term with largest amplitude has n (x )=2N -1, hence, after the k -th application of U its amplitude will be c x /2k . Thus, if k is large enough only the term corresponding to the searched answer will have considerable amplitude and, after amplitude amplification, the searched answer will be obtained with high probability ina single set of measurements. For example, choosing x c for all x , the largest amplitude after kusage of U(before amplitude amplification) is min x c while the second largest amplitude will bemin 2k x x c c . The oracle in the amplitude amplification is applied /(4 ) times, where [9]sin k.If k is large enough, then 2Ngood p . Obviously, the efficiency of the proposed algorithm is equal to theefficiency of the amplitude amplification.3. Quantum algorithm for finding a lower bound of DA Diophantine equation is a polynomial equation with any number of unknowns and with integercoefficients. For example, (x +1)n +(y +2)n +(z +3)n -Cxyz =0, where C and n . Since there is not a universal process to determine whether any Diophantine equation accepts or not integer solutions, the best that one can do is to use a brute-force method. In this case, one can not determine the probability of finding a Diophantine equation that accepts integer solutions, D , exactly, but it is possible to determine a lower bound for it. In this direction, the quantum algorithm proposed can be used to implement a brute-force attack (using the intrinsic quantum parallelism) and the accuracy of the answer obtained is limited by the amount of qubits used, the larger the amount of qubits used the closer to D is the obtained answer. Since only a finite amount of qubits can be used, the answer obtained is simply a lower bound of D . Since the (infinite) set of Diophantine equations considered is enumerable, we will use integer numbers to enumerate the Diophantine equations. The quantum circuit for the proposed quantum algorithm is shown in Fig. 2. In this quantum circuit, we assume that the set of Diophantine equations considered has only three unknowns (x ,y ,z ), however, the extension to a larger number of unknowns is straightforward.(10)(11)(12)(13)(15)(16)(14)(17)31126354,,32126543,,3125643,,,,,,0000,,,,000,,,,,,00lM lxyz px y z Ml xyz p px y z lxyz p px y zx y z p c x y z c x y z D x y z p c x y z D x y z y z4125634,,,,51126534,, ,,,,,,,,,,,,,,0,,,,,,,,1p p i j mxyz p p px y z x y z xyzp i j mp i j mpx y zi j mD x y z D x y z c x y z D x y z y z D x y z cx y zD x y z y z D x y z !62126543,, ,,,,,,352317132,,,,,,01,,,,0,,2,,,,p p i j mpp s s s s s s opts lxyzp i j mpx y zi j mD x y z D x y z t p p p p p pM opt opt opt p opt opt opt xyz s M xyz p pcx y zD x y z y z c x y z D x y z c n x y z x y z D x y !4634353,,,,,,010p p popt opt opt l Mpx y z x y z x y z z !!Finally38126354,,2133163542 ,,,,,,,,0000,,0000,,2,,pps s s opt sp p popt opt opt lM lxyz px y zt p p popt opt opt xyz s l MlM pxyz x y zx y z x y z U c x y z c x y z p c n x y z x y z !In (17), 1 n (x ,y ,z ) 23M is the number of elements that obey |D p (x,y,z )| |D p (x’,y’,z’)| for a given x ,y ,z and all x’,y’,z’. Thus, the better the solution the larger is the value of n (x ,y ,z ). We assume that, for the Diophantine equation number p there are t p minimums. Moreover3,,2s s sp p pMopt opt opt n x y z for s =1,2,…,t p . Thestates !i i =1,2,3,4 and ! are states with undesired terms. Now, using k -times the gate U together with the multi-controlled CNOT gates, the quantum state just before the quantum amplification is:(20)(19)(18)3312635421 ,,,,,,,,,,2,,0000p p s s s opt sp p popt opt optt kp p p M l Mlopt opt optxyz xyz ps x y zx y z x y z p c x y z c n x y z x y z"The state " represents the uninteresting terms. At the amplitude amplification, the oracle recognizes the state 0 3M 0 in the fifth and sixth quantum registers. Therefore, only the first term in (18) will have their amplitudes amplified. Looking closer the first term in (18), one sees that the amplitude of one of the searched answers is p opt sxyz c (comparing to the single variable case in Section 2, we have n (x,y,z )=23M for,,,,p p popt opt opt x y z x y z ). The second term with largest amplitude has n (x ,y ,z )=23M -1, hence, after the k -thapplication of U its amplitude will be c xyz /2k . Thus, if k is large enough only the term corresponding to the searched answer will have considerable amplitude and, after amplitude amplification, it will be obtained with high probability in a single measurement. For example,choosing xyz c for all xyz , thelargest amplitude after k usage of U (before amplitude amplification)is p opt sxyz c thesecond largest amplitude will be 2popt sk xyz xyz c c . The oracle in the amplitude amplification is applied/(4 ) times, wheresin k.If k is large enough, then 32Mgood p p t . The efficiency of the proposed algorithm is equal to theefficiency of the amplitude amplification. Thus, the final state after the amplitude amplification is1,,,,ps s ss s st p p pp p pend opt opt opt p opt opt opt ps y z D x y z errIn (20) one can see that, for each one of the 2N Diophantine equations, the algorithm calculate the minimums values testing 2M different values for each unknown. Moreover, the term err represents the remained unwanted states due to the non ideal amplitude amplification.In order to calculate the lower bound of D , we use the state (20) as input of a quantum countingalgorithm whose oracle recognizes a zero in the last register of (20), that is,,,0p p pp opt opt optD x y z .The quantum counting algorithm returns the number of elements in the database that pass in the oracle test. Let us name this value by r (N ,M ). Hence,(21),lim ,2N D N M r N M #$and a lower bound for D is simply ,2estND r N M .4. DiscussionsThe problem to decide if a given Diophantine equation has or not integer solutions is, according toChurch-Turing computability thesis, an undecidable problem. In fact, this problem is related to the halting problem for Turing machine: The Diophantine equation problem could be solved if and only if the Turing halting problem could be [10]. Since there is not a universal process to decide if a given program will halt or not a Turing machine, the best that one can do is to run the program and wait for a halt. The point is: one can never know if he/she waited enough time in order to observe the halt. The Diophantine equation problem has a similar statement. Since there is not a universal procedure to decide if a given Diophantine equation accepts an integer solution, the best that one can do in order to check if it accepts or not an integer solution, is to test the integer numbers. The point here is: one can never know the answer because there are infinite integers to be tested. Associated to the halting problem is the Chaitin number , the probability of a given program to halt the Turing machine [11-17]. The number is an incompressible number and it can not be calculated. Similarly, one can define the probability of finding a Diophantine equation with integer solutions, D . Obviously, D is also a number that can not be calculated, because the knowledge of D implies in the knowledge of a way to decide if any given Diophantine equation accepts or not any integer solution that, by its turn, implies in the knowledge of and in the solution of the halting problem. As happens with , it is possible to calculate classically a lower bound for D , however, it must be a brute-force algorithm. Classical algorithms for calculation of D will differ basically in the method that the zeros of the Diophantine equation are obtained. The quantum algorithm here proposed is also a brute-force algorithm but its advantage is the quantum parallelism, since several Diophantine equations are tested simultaneously.4. ConclusionsIt was proposed a new quantum algorithm for finding the minimum of a function that requires only one measurement. This is important since the complete circuit is simplified and measurements of qubits are not noise free. This algorithm is an asymptotic quantum search. As an example of its application, we constructed a quantum algorithm for finding a lower bound for the probability of finding a Diophantine equation that accepts integer solutions. A lower bound can also be calculated using a classical computer,however, our algorithm is more efficient since it can test 2N(for N qubits) Diophantine equations simultaneously. At last, the algorithm proposed requires only one measurement, after the quantum counting stage.AcknowledgeThe authors thank the anonymous reviewer for useful comments.References1.Grover, L. V.: A fast quantum mechanical algorithm for database search, in Proc., 28th Annual ACM Symposium on the Theory of Computing, New York, pp. 212 (1996).2. Grover, L. V.: Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett., 79, pp. 325 (1997).3. M. A. Nielsen, and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge Univ. Press, Cambridge, ch. 4 and 6 (2000).4. Dürr C., and Høyer, P.: A quantum algorithm for finding the minimum, arXive:quant-ph/9607014 (1999).5. Ahuja, A., and Kapoor, S.: A quantum algorithm for finding the maximum, arXive:quant-ph/9911082 (1999).6. Boyer, M., Brassard, G., Høyer, P., and Tapp, A.: Tight bounds on quantum searching, arXive:quant-ph/9605034 (1996).7. Kowada, L. A. B., Lavor, C., Portugal, R., and de Figueiredo, C. M. H.: A new quantum algorithm to solve the minimum searching problem, International Journal of Quantum Information, Vol. 6, no. 3, 427 - 436, 2008.8. Kaye, P., Laflamme, R., and Mosca, M.: An introduction to Quantum Computing, 1st Ed., Oxford University Press, 2007.9. Oliveira, D. S., and Ramos, R. V.: Quantum Bit String Comparator: Circuits and Applications, Quantum Computers and Computing, vol. 7, no. 1, 17-26, 2008.10. T. D. Kieu, Quantum algorithms for Hilbert’s tenth problem, – quant-ph/0110136, 2003.11. C. Calude, Theories of Computational Complexity, North-Holland, Amsterdam, 1998.12. G. Chaitin, Meta Math!: the quest for omega, Pantheon Books, 2005.13. G. Chaitin, Irreducible Complexity in Pure Mathematics, Preprint at (/math.HO/0411091), 2004.14. G. Chaitin, Information-theoretic computational complexity, IEEE Trans. on Inf. Theory, IT-20, 10, 1974.15. C. Calude, Information and Randomness, Spring-Verlag, Berlin, 1994.16. G. Chaitin, Algorithmic Information Theory,1a Ed. Cambridge University Press, 1987.17. G. Markowsky, Introduction to algorithmic information theory, J. of Universal Comp. Science, 2, no. 5, 245, 1996.。

算法是一把双刃剑作文材料英文回答：Algorithm is indeed a double-edged sword. On one hand, algorithms have greatly improved our lives and brought us convenience and efficiency. For example, recommendation algorithms on e-commerce platforms can help us findproducts that we may be interested in, saving us time and effort. Search algorithms enable us to quickly find information on the internet, making research and learning more accessible. Algorithms also play a crucial role in various industries, such as finance, healthcare, and transportation, optimizing processes and improving outcomes.However, algorithms also have their downsides. Onemajor concern is the issue of algorithmic bias. Algorithms are created by humans and are based on data that maycontain inherent biases. This can lead to unfair outcomes, such as discriminatory hiring practices or biased loan approvals. Another concern is the potential for algorithmsto invade privacy. With the increasing amount of data being collected and analyzed, algorithms have the power to infer personal information and make predictions about individuals, raising concerns about surveillance and data misuse.Furthermore, algorithms can also perpetuate echo chambers and filter bubbles. Recommendation algorithms tend to show us content that aligns with our existingpreferences and beliefs, limiting our exposure to diverse perspectives. This can reinforce our existing biases and hinder critical thinking and open-mindedness.中文回答：算法确实是一把双刃剑。

Evolutionary AlgorithmsJuan Carlos Granados NarbonaCommunication and Operating Systems GroupBerlin University of Technologyjcgranad@cs.tu-berlin.deAbstract.Evolutionary computation is a rapidly growingfield duringthe last decade,althougth his origins can be traced back to the late1950’s.A subset of evolutionary computation are evolutionary algorithms(EA).This paper suplies a brief survey of their earlier beginnings,de-sign and different implementations like genetic algorithms(GA),evolu-tionary strategies(ES)and evolutionary programming(EP).Specific ex-amples and a practical case will be also commented.Keywords:evolutionary algorithms,evolution strategies,genetic algorithms,ge-netic programming1IntroductionWhy use evolution as a method for solving computational problems?As we know, many computational problems require searching a huge number of possibilities for solutions.By other problems man may demand complex solutions that are difficult to program by hand or using traditional algorithms.Often the effective use of parallelism is suggested for exploring different possibilities in a effective way.Or our computer programm needs to be adaptive for a continous well per-foming in a changing environment.Here is the point,where the mechanisms of evolution seem to be well suited apporting new concepts and methods inspired by biological evolution.In the seminar”Organic Computing-summer semester2006”we discuss re-lated themes as follows.The next section2illustrates the concept of evolution and evolutionary algorithmsIn third section3the general structure of EAs,their most important elements and how they work is described.The fourth Section4, provides a short description of well-known EAs,special characteristics and a criteria comparison of them.After that,we comment a practical case5of us-ing evolutionary algorithms to optimize a real search problem.Finally,the last section6presents our conclusions.2Fundations of evolutionary algorithmsIn the following we present some elementary definitions.2.1EvolutionEvolution(t.:evolvere=evolve,deployment,expansion,progression)could be defined as a process that results in heritable changes in a population spread over many generations[1].The evolution is bound at three necessary conditions.1.the presence mentioned by elements abled to replicate,2.a varying copying accuracy,known as variation,as well as,3.a different probability of each variant to arrive as element into that samplefrom which the following population is built up:selection.The term was introduced1774by Swiss natural scientist Albrecht of Haller (1708-1777)for its conception of the development of humans.The modern understanding of evolution wasfirst presented1858in a collective paper by Charles Darwin(1809-1882)and Alfred Russel Wallace(1823-1913)and popularized in Darwin’s book”The Origin of Species”(1859).It is based on the theory of natural selection,a process by which individual organisms with favorable traits are more likely to survive and reproduce.The evolution theory at present is a complex,scientific theory of biology.It means that all life has a common descent and the variety of the species has been developed by evolution.Basic statements of the evolution theory are:-Evolution always takes place-Evolution is not reversible(Louis Dollo law)[2](individual structures or achievements can copy old conditions but the underlying genes no more the same structure).-Evolution is not purposeful in the scientific sense(it takes place thus no development for a recognizable purpose).-The evolution affects all levels of the animated world:from the molecule to the ecological system.2.2Definition of Evolutionary algorithmsEvolutionary algorithm is a generic term used to indicate any population-based optimization algorithm that uses mechanisms inspired by biological evolution, such as reproduction,mutation,recombination(evolution or variation opera-tors),natural selection and survival offittest.Candidate solutions to the optimization problem should be seen as individuals in a population and thefitness(cost)function as the environment within the solutions take place.Each individual is evaluated by afitness function.Then the population evolve towards better and better individuals via operators based on natural selection,i.e.survival and reproduction of thefittest,and genetics, e.g.crossover and mutation operators-Goldberg(1989)[3].After repeated ap-plication of the above operators the new population defines a new generation. The evolution process reiterates,till a determinated objetive is reached,such as an apropiate solution(individual)or a specific number of generations(turns)has been delivered.3Theory of evolutionary algorithms3.1Structure of an evolutionary algorithmEvolutionary algorithms are stochastic search methods,that follow the natu-ral biological evolution process.At the beginning of the computation process a number of individuals(the population)are randomly initialized.The objective function,wich describes our optimization search goal,is then evaluated for these individuals.Thefirst/initial generation is produced.If the optimization criteria are not met the algorithm start the creation of a new generation:it selects individuals according to theirfitness for the production of offspring(parent selection mechanism)and recombine them to produce offspring. Mutation of all offspring can also be applied with a certain probability.After this thefitness of the offspring is again computed and the offspring are inserted into the population replacing the parents und producing a new generation.This cycle is performed(seefigure1)until the optimization criteria are reached.Fig.1.Structure of an evolutionary algorithm.Taken from:Introduction to Evo-lutionary Computing-Springer Verlag[4]In correlation to this description a pseudo-algorithm,that can be applied to all EAs,can be described as follow:–BEGIN1.Generation t:=0;2.inititialite the population P(t);3.while not Termination criterion do•evaluate(evaluation and parent selection)the population P(t);•next P’(t)=variation(recombination/mutation)over P(t);•evaluate(evaluation)P’(t);•P(t+1)=select(survivor selection)P’(t)Q1;•Generation t=t+1;4.end while;3.2Components of an evolutionary algorithmThis are the main components of an evolutionary algorithm:(seefigure2)Fig.2.Diagram of the components of an EA.1.Population The primary parameters for controlling the genetic algorithmare the population size and the maximum number of generations to be run.Although EAs can handle with very huge populations,it is used to define a fixed maximum of individuals.2.Representation of individuals”link”the real world(original problemcontext)to the EA world(problem-solving space where evolution takes place)(figure3).We distinguish also between objects and their parameter forming possible solutions within the problem context(phenotype)and their encoding(genotype).This encoding/decoding function must be also invert-ible:to each genotype there has to be at most one corresponding phenotype.Selecting a representation scheme that facilitates solution of the problem by1with P as population and Q the quota of parent individuals,that sould survive the next generation,in order to preserve specific criteriaFig.3.Phenotype,genotype and encoding/decoding functionan EA often requires considerable insight into the problem and good judg-ment.3.Evaluation function The evolutionary process is driven by thefitness mea-sure.This assigns afitness value to each individual,which is the basis for the selection process.Thisfitness value should be similar for alike individuals with the same properties.4.Parent selection mechanism Selection determines,which individuals arechosen for mating(recombination)and how many offspring each selected individual produces.Thefirst step isfitness assignment by:The actual se-lection is performed in the next step.Parents are selected according to their fitness by means of one of the following algorithms:–rank-basedfitness assignment[5]:the population is sorted according to the objective values.Thefitness assigned to each individual depends only on its position in the individuals rank and not on the actual objective value.–proportionalfitness asignment[6]•roulette-wheel selection:this method maps the individuals to con-tiguous segments of a line.Each individual’s segment is equal insize to itsfitness.A random number is generated and the individualwhose segment spans the random number is selected.The processis repeated until the desired number of individuals is obtained.Thismethod is analogous to a roulette wheel with each slice size propor-tional to thefitness.•Stochastic universal sampling:the individuals are assigned to con-tiguos sections of a line exactly as the roulette-wheel selection.Dif-ferent it is that a number of pointers over the line are distributedevenly here.The number of individuals to be selected(n)correspondsto the number of pointers.Then the distance between the pointersare1/n and the position of thefirst pointer is given by a randomlygenerated number in the range[0,1/n].The individuals whose seg-ment includes the pointer are selected.–tournament selection:tournaments between several individuals are ac-complished.Winner of a tournament and thereby selected is the best individual with the”highestfitness”.So many tournaments take place, as individuals are to be selected.–truncation selection:the individuals are sorted according to theirfitness.All individuals with afitness,which is larger than afixed threshold,are selected.Therefrom only the best individuals are selected.5.Variaton operators–Recombination/Crossover produces new individuals in combining the information contained in the parents(mating population).Depend-ing on the representation of the variables of the individuals the following algorithms[7]can be applied:-Real valued recombination4:∗discrete recombination:performs an exchange of variable valuesbetween two individuals.∗intermediate recombination:the variable values of the offspringare chosen somewhere around und between the variable valuesof the parents.∗line recombination:generates variable values at any point on theline defined by the parents.-Binary valued recombination(crossover)5:∗single-point crossover:one crossover position relative to the num-ber of variables of the individuals is randomly selected and thevariables are interchanged between the individuals about thispoint.∗multi-point crossover:m crossover positions are selected(with noduplicates)and sorted.After that the variables between succes-sive points are exchanged to create two new offsprings.∗uniform crossover:makes use of a randomly created mask withsame length as variables exists.Teh parity of the bits in the maskhints which parent will supply the offspring with which bits.∗suffle crossover:like uniform crossover,but the variables are ran-domly shuffeld in both parents before exchange and unshuffledin offspring after crossover.Fig.4.Real valued recombination.After Pohlheim[8]∗crossover with reduced surrogate:a crossover point takes placeat every point,at which the variable values of the parents differfrom another.–Mutation The mutation operator simply changes the value of a gene toa new random value.The purpose of the mutation operator is to preventthe genetic population from converging to a local minimum and to intro-duce to the population new possible solutions.This is also necessary to raise the genetic diversity of individuals in the population(mutation can generate gene values that are not present in the current population).It randomly alters each individual with a(usually)small probability. Both crossover and mutation are stochastic operators,applied with user-defined probabilities.The probability of mutation,depending of selectedEA,is usually much lower than that of crossover.Fig.5.Binary valued recombination.After Pohlheim[8]6.Survival selection mechanism(reinsertion).After the offspring is pro-duced and evaluated,it must be inserted into the population(figure6).It should be differentiate how many and which offspring individuals will be inserted into the population and which individuals of the population should be replaced.A selection of the offspring must be only accomplished,if not all produced individuals are to be inserted into the population.The parameter for it is the reinsert rate(insertion rate).By elitest reinsertion it is guaran-Fig.6.Schema of survival selection mechanism.After Pohlheim[8] teed that the best individuals of the population remain in the population and are only replaced,if better individuals were found.7.Termination criterion Each run of the EA requires specification of a ter-mination criterion for deciding when to terminate a run and a method ofresult designation.One frequently used method is to designate the best in-dividual obtained in any generation of the population during the run(i.e., the best-so-far individual)as the result of the run.4Known Evolutionary algorithmsMore than sixty years ago,about1940,long before the breakthrough of computer began the idea of appling the evolution principles,introduced by Darwin,into the process of solving problems.With the incoming of computers into engineer-ing processes,this idea was revived into”evolutionary systems”:using evolution and its principles as search and optimization tool for a given problem.So began the evolutionary computing to produce interest in the scientist com-munity.Some scientists deploy such evolutionary methods only as an study,how evolution takes place in nature and how this natural operators(genetic variation and selection)could be imported into computer systems.Other just developed evolutionary algorithms to solve their specific problems.Many other deployed al-gorithms for machine learning or optimization.Today evolutionary algorithms or evolutionary computing has become a very interestingfield of organic computing, with genetic algorithms,evolutionary strategies and evolutionary programming as its well-known representatives.In the following we show these evolutionary algorithms and their main charac-teristic features.4.1Genetic Algorithms”A Genetic algorithm(GA)is a mathematical search technique based on the principles of natural selection and genetic recombination[9]”.Genetic algorithms were invented in the1960s by John Holland and developed with help of his students and colleagues at the University of Michigan in the 1960s and the1970s.Their purpose was to study the natural adaption and im-port it into computer systems and it was presented in his book”Adaption in Natural and Artificial Systems”from1975.Genetic algorithms are so far generally the best and most robust kind of evo-lutionary algorithms.They are robust search algorithms and efficient when the search space ist large or complex,no mathematical analysis ist avaliable or tra-ditional search methods fail.GAs get also good results when domain knowledge is marginal or too difficult to encode into the search space.Representation and a significativefitness evaluation function are also very important for the GAs successfully application.The genetic algorithm uses a constant size population(set)of individuals(cro-mosomes)and applies mainly the crossover varation operator to create a new generation.Individuals,seens as possible solutions to the problem and each as-sociated with anfitness value,are encoded using afixed length alphabet usually as binary strings(bit-strings)of0s and1s(gene).Mutation,if used,consists ofa bit-flip operation over each separately gene of the individuals and it is applied with a small probability.4.2Evolutionary StrategiesEvolution strategies(ES)were introduced by Rechenberg[10](1965,1973)and further developed by Schwefel[11](1975,1977)at the Technical University of Berlin.Motivation of their study was,from the beginning,to solve engineering design problems:Rechenberg and Schwefel developed ES in order to conduct successive wing tunnel experiments for aerodynamic shape optimization(e.g.Rechenberg developed a method to optimize realvalued parameters for devices such as air-foils).Thefield of evolution strategies has remained an active area of research and algorithm design to solve specific problems,mostly developing independently from thefield of genetic algorithms(although recently the two communities have begun to interact)[12].A short review of ES is illustrated by Back,Hoffmeister,and Schwefel1991.)[13]The representation used in evolutionary strategies,is afixed-length real-valued vector.As with the bit-strings of genetic algorithms,each position in the vector corresponds to a feature of the individual.ES often uses a smaller population(e.g.under20members)and prioritizes mutation over crossover as variation operator.4.3Evolutionary ProgrammingFogel,Owens,and Walsh[14]developed evolutionary programming(EP)ac-tually as algorithms to solve specific problems.They used the concept offinite state machines,which were evolved by randomly mutating state transition di-agrams and selection of thefittest as representation of candidate solutions to given task.”The representation used in ES is typically stringently connected to the problem domain,usually as afixed-length real-valued vector.The primary difference between evolutionary programming and the other ap-proaches(GA,GP,and ES)is that no exchange of material between individuals in the population is made.Therefore,only mutation operators are used.A typ-ical selection method is to select every individual as parent(n),mutate then to form the offspring(n)and probabilistically select,the half of the2n individuals as survivors and member of the next generation.[..]”[15]4.4Learning Classifier SystemsA Learning Clasifier System[16](figure7),or LCS,is a machine learning system with close links to reinforcement learning and genetic algorithms.They werefirst described by John Holland and consist of a population of binary rules on whicha genetic algorithm altered and selected the best rules.A rule utility is decided by a reinforcement learning technique(don’t usefitness function).The data/information of the environment are coded by the detectors(Detektoren in german)into a(or several)binary message.This messages can apply to the condition section of classifier from the classifier list,which write the message into the message list,which can activate again classifier etc.If this procedure are scheduled,the remaining messages in the message list are converted in actions by the effectors(Effektoren).The classifier is evaluated by one credit assignment algorithm and combined from a genetic algorithm to new classifier.[17]A classifier system is able to”classify”its environment and create rules dynam-ically,therefore able to adapt to differing situations on thefly.(More Information about LCS could be found at:[18])Fig.7.Structure of a classifier Systems4.5Genetic ProgrammingGenetic Programming(GA)is a special case of a genetic algorithm.Instead of by bit strings,the individuals are represented by syntax trees,with rule conditions and/or attirbute values in the leaf nodes and functions(relational,logical or mathematical operators)in the internal nodes.This individuals are maped to programs.Programs can be generated also automatically with the help of genetic programming8.4.6Outlook and comparisonSpecific examples of EAs are given below.Most of these techniques are similar in spirit,but differ in the details of their implementation and the nature of the particular problem to which they have been applied.Fig.8.Genetic Programming”Comparison:–Genetic algorithm:this is the most popular type of EA.One seeks the so-lution of a problem in the form of strings of numbers(traditionally binary, although the best representations are usually those that reflect something about the problem being solved-these are not normally binary),virtually always applying recombination operators in addition to selection and muta-tion;–Evolutionary programming:like genetic programming,only the structure of the program isfixed and its numerical parameters are allowed to evolve;–Evolution strategy:works with vectors of real numbers as representations of solutions,and typically uses self-adaptive mutation rates;–Genetic programming:here the solutions are in the form of computer pro-grams,and theirfitness is determined by their ability to solve a computa-tional problem.–Learning classifier system:instead of a usingfitness function,rule utility is decided by a reinforcement learning technique.”Taken from wikipedia-[19]+Representation Used Operators Population size Choice mechamism GA Bit-String Recombination*Fixed ProbabilisticMutationES Vector of Mutation*Fixed Deterministic floating-point number RecombinationEP Vector of Mutation*Fixed Deterministic floating-point number RecombinationGP parse tree Recombination*Variable ProbabilisticMutationTable1.Criteria comparison of EAs-*marks the most relevant operators5A practical example:getting the best with evolutionary algorithmsIn the following we discuss the paper from Neri[20]to display how EAs can be applied to optimize searching processes.In his paper,Neri defines the detec-tion of intrusions over computer networks as”the task of detecting anomalous pattern of network traffic”.To display this association,he compares two mod-els for adquisition of data traffic(one based on a distributed genetic algorithm -REGAL-and one based on”greedy”heuristic-RIPPER-)and show how the network data representation affects the perfomances of the trafic models.Neri uses as basis:–traffic data from Information Exploration Shootout Project(IES)[21],provided as a large set of network logs containing intrusion attemps as well as normal traffic.This data can be partitioned–two learning systems REGAL as optimiser of former studies[22]and RIPPER as a benchmark to compare the optimization results.REGAL[23](RElational Genetic Algorithm Learner)is”a concept learning sys-tem based on a distributed genetic algorithm that learns First Order Logic multi-modal concept descriptions.REGAL uses a relational database to han-dle the learning examples that are represented as relational tuples”[24].It was developed by Giordana and Neri at the”Universita di Torino”5.1Advance optionsSo displays Neri the optimization process using REGAL in analogy RIPPER, used by Lee,Stolfo and Mok in their studie.[25].An iterative procedure that involves pattern mining and comparison,feature con-struction from patterns,and model building and evaluation is thus employed.In each iteration,a different combination of axis attribute and reference attribute is selected.The choices are limited among the essential attributes,that is,service, dst host,src dst,or src port.After comparing results,he decides to develop a”more compact representation for the packets that consists in mapping a subset of feature’s values into a single value...This compression-based representation is then a valuable way of increass-ing classification perfomances without introucing complex feature that involves additional processing overhead”.[20]This is the main data-mining process(figure9)Fig.9.Overview of the minig data process.After Neri and Giordana[22]6ConclusionsIn this paper the structure and how evolutionary algorithms work has been explained and commented.Also a short milestone of EAs has been presented.As seen,the steady deployment process of Evolutionary algorithms began almost50 years ago.Genetic algortihms,evolutionary strategies and genetic programming are still the well-known framework of evolutionary algorithms.But new concepts as genetic programming and classifiers systems are meeting with success and give the impression that thisfield of the evolutionary computation is still gaining an importance.International Conferences take annually place and new domains and common applications like automatic programming,social systems,optimization,immune systems and machine learning meet with approval the advantages,adaptibiliy and diversity of evolutionary algorithms.References1.What is evolution?by laurence moran-copyright1993-1997[online,cited2006/08/10].Available from:/faqs/ evolution-definition.html2.Thienemann, A.:Die chironomidengattung pseudosmittia und das dolloschegesetz.Acta Biotherica7(3-4)(1943)117–134.Available from:http://www./openurl.asp?genre=volume&id=doi:10.1007/BF01578158 3.Goldberg,D.E.:Genetic algorithms in search,optimization,and machine learning.Addison-Wesley,Reading,MA(1989)4.Eiben,A.E.,Smith,J.E.:Introduction to Evolutionary Computing.SpringerVerlag(2003)5.Baker,J.E.:Adaptive selection methods for genetic algorithms.In:Proceedingsof the1st International Conference on Genetic Algorithms,Mahwah,NJ,USA, Lawrence Erlbaum Associates,Inc.(1985)101–1116.Goldberg,D.E.:Genetic Algorithms in Search,Optimization and Machine Learn-ing.Addison-Wesley Longman Publishing Co.,Inc.,Boston,MA,USA(1989) 7.M¨u hlenbein,H.,Schlierkamp-Voosen,D.:Predictive models for the breeder geneticalgorithm:I.continuous parameter optimization.Evolutionary Computation1(1) (1993)25–498.Pohlheim,H.Entwicklung und systemtechnische anwendung evolutionrer al-gorithmen-abbildungsverzeichnis[online,cited2006/08/10].Available from: /diss/text/diss pohlheim ea lof.html9.Holland,J.H.:Adaptation in Natural and Artifical Systems.University of MichiganPress,Ann Arbor,MI(1975)10.Rechenberg,I.:Evolutionsstrategie:Optimierung technischer Systeme nachPrinzipien der biologischen Evolution.frommann-holzbog,Stuttgart(1973)Ger-man.11.Schwefel,H.P.:Evolutionsstrategie und numerische Optimierung.PhD thesis,Technische Universit¨a t Berlin,Berlin,Germany(1975)German.12.International society for genetic and evolutionary computation[online,cited2006/08/10].Available from:13.B¨a ck,T.,Hoffmeister,F.,Schwefel,H.P.:A survey of evolution strategies.In Belew,R.K.,Booker,L.B.,eds.:Proc.of the Fourth Int.Conf.on Genetic Algorithms, San Mateo,CA,Morgan Kaufmann(1991)2–914.Fogel,L.J.,Owens,A.J.,Walsh,M.J.:Artificial Intelligence Through simulatedEvolution.John Wiley and Sons,New York(1966)15.Cellular evolutionary algorithms site[online,cited2006/09/25].Available from:http://neo.lcc.uma.es/cEA-web/16.Bull,L.:Applications of Learning Classifier Systems.SpringerVerlag(2004)17.Classifier systems and economic modeling[online,cited2006/08/10].Availablefrom:/apl96/mitl.htm18.Learning classifier systems(lcs)bibliography[online,cited2006/08/10].Availablefrom:/∼kovacs/lcs/search.html19.Evolutionary algorithms-wikipedia[online,cited2006/09/25].Available from:/wiki/Evolutionary algorithm20.Neri,F.:Evolutive modeling of tcp/ip network traffic for intrusion detection.In:Real-World Applications of Evolutionary Computing,EvoWorkshops2000: EvoIASP,EvoSCONDI,EvoTel,EvoSTIM,EvoROB,and EvoFlight,London,UK, Springer-Verlag(2000)214–223rmation exploration shootout project-ies[online,cited2006/08/10].Availablefrom::8080/22.Neri,F.,Giordana,A.:A parallel genetic algorithm for concept learning.InEshelman,L.J.,ed.:Proc.of the Sixth Int.Conf.on Genetic Algorithms,San Francisco,CA,Morgan Kaufmann(1995)436–44323.Machine learning programs-regal[online,cited2006/08/10].Available from:http://www.di.unito.it/∼mluser/programs.html24.Giordana,A.,Neri,F.:Search-intensive concept induction.Evolutionary Compu-tation3(4)(1996)375–41625.Lee,W.,Stolfo,S.J.,Mok,K.W.:Mining in a data-flow environment:experience innetwork intrusion detection.In:KDD’99:Proceedings of thefifth ACM SIGKDD international conference on Knowledge discovery and data mining,New York,NY, USA,ACM Press(1999)114–124.doi:/10.1145/312129.312212。

Chapter 1 练习复习题1.定义一个基于图灵模型的计算机。

答：Turing proposed that all kinds of computation could be performed by a special kind of a machine. He based the model on the actions that people perform when involved in computation. He abstracted these actions into a model for a computational machine that has really changed the world. 图灵模型假设各种各样的运算都能够通过一种特殊的机器来完成，图灵机的模型是基于各种运算过程的。

图灵模型把运算的过程从计算机器中分离开来，这确实改变了整个世界。

2.定义一个基于冯·诺伊曼模型的计算机。

答：The von Neumann Model defines the components of a computer, which are memory, the arithmetic logic unit (ALU), the control unit and the input/output subsystems.冯·诺伊曼模型定义了计算机的组成，它包括存储器、算术逻辑单元、控制单元和输入/输出系统。

3.在基于图灵模型的计算机中，程序的作用是什么？答：Based on the Turing model a program is a set of instruction that tells the computer what to do.基于图灵模型的计算机中程序是一系列的指令，这些指令告诉计算机怎样进行运算。

4.在基于冯·诺伊曼模型的计算机中，程序的作用是什么？答：The von Neumann model states that the program must be stored in the memory. The memory of modern computers hosts both programs and their corresponding data.冯·诺伊曼模型的计算机中，程序必须被保存在存储器中，存储程序模型的计算机包括了程序以及程序处理的数据。