For my students in Czech - Biologically inspired algorithms
For my students in Czech - Biologically inspired algorithms
Literatura
1.Kvasnička V., Pospíchal J., Tiňo P., Evolučné algoritmy, STU Bralislava, ISBN 80-227-1377-5, 2000
2.Mařík V. Štěpánková O., Lažanský J., Umělá inteligence IV, Academia, Praha, ISBN 80-200-1044-0, 2004
3.Mařík V. Štěpánková O., Lažanský J., Umělá inteligence III, Academia, Praha, ISBN 80-200-0472-6, 2001
4. Zelinka I., Včelař F., Čandík M., Fraktální geometrie – principy a aplikace, BEN, 2006, 160 p., ISBN 80-7300-191-8
5. Fatima Cvrčková, Úvod do praktické bioinformatiky, Academia, Praha, 2006
Lectures:
1.Evolutionary algorithms 1. The current state of the field softcomputing, fuzzy logic, neural networks, evolutionary computing (EVT). Classification of evolutionary computation, historical facts, current trends in EVT. The central dogma, according to Darwin, and EVT
Mendel.
2. Evolutionary Algorithms 2. No Free Lunch Theorem. Computational complexity and physical limitations algorithms. Multipurpose optimization and Pareto set.
3. Evolutionary algorithms 3. Restrictions placed on the utility function and individual parameters. Penalties and its impact on the geometry of the objective function. Working with real, integer and discrete values of individual parameters. Genetic algorithms. GA terminology. Principle
activities, Hybrid GA, messy GA, parallel GA, migration and diffusion models.
4. Evolutionary algorithms 4. Evolutionary Strategy. No-man (1 +1)-EC.Multi-EC (μ + Λ)-ES and (μ, λ)-ES. Multi-EC (μ + λ)-ES and (μ, λ)-ES. Adaptive EC.Particle swarm (Particle Swarm). Search suspended (Scatter Search). Ant colony optimization (Ant Colony Optimization).
5. Evolutionary algorithms 5. SOMA: Self-Organizing Migrating Algorithm principle of operation and strategies used by the algorithm: ATO, ATR ATAA and ATA. Differential evolution principle activities and used versions: DE/best/1/exp, DE/rand/1/exp, DE/rand-to-best/1/exp, DE/best/2 / exp DE/rand/2/exp, DE/best/1/bin, DE/rand/1/bin, DE/rand-to-best/1/bin, DE/best/2/bin, DE/rand/2/bin. SOMA, DE and permutation test problems.
6. Evolutionary algorithms 6. Techniques of Genetic Programming: Genetic Programming, grammatical evolution. Alternatives: analytical programming, Probabilistic Incremental Program Evolution - PIPE, Gene Expression Programming, Programming Multiexpression
and more.
7. Evolutionary Hardware (EH). Inspiration in biology. Computing devices.Reconfigurable equipment. Evolutionary design and digital circuits. EH and cellular automata. Polymorphous electronics.
8. Cellular Automata (BA) and complex systems. Introduction, Formalism BA Dynamics and classification according to Wolfram's cellular automata, Conway's Game of Life, using BA modeling.
9. Artificial life. Basic definitions and existing systems and models. Tierra, biomorf, Sbeat, Sbart, Eden, Galapagos ... Self-reproducing automata according to Turing and von Neumann. Langton's loop, computer viruses and artificial life. Artificial Life and edge
chaos (according to Kaufmann)
10. Neural Networks (ANN). History and basic principles of NS. The training set and its use NS. The basic types of networks and their applications to different types of problems.
11. Fractal geometry. History, definition of fractal, basic types of algorithms that generate fractals. Fractal dimension, interpolation and compression. Developmental systems and artificial life. L systems, turtle graphics, parametric L-systems, L-systems from the perspective of fractal geometry.
12. Immunological systems (IS). The principle of the IS, the IS limits, algorithms implementing IS imunotronics.
13. Swarm Intelligence (SI). Basic concepts and definitions, representative algorithms SI - Particle Swarm, scatter search, ant colony optimization, swarm robotic, artificial evolution complex systems.
Exam questions
1. Term artificial intelligence (history, definitions, ...) softcomputing and its breakdown (fuzzy logic, neural networks, evolutionary computing). Classification of evolutionary computation techniques, historical facts (Darwin, Mendel, Turing, the Barricelli, ...), current trends in the field of EVT.
2. Central dogma EVT by Darwin and Mendel and its application in the form of EVT techniques. Explain the general evolutionary cycle. Explain the basic concepts: individual (structure and representation), the population and their creation, fitness, objective function, representation of individuals. Gray code (design advantages over the standard binary code, Hamming barrier), No Free Lunch theorem and its impact on the use of EVT. How to evaluate the performance of the lens of evolutionary algorithm and compare two or more different evolutionary algorithms?
3. Classification of optimization methods (enumerative, deterministic, ..., heuristic) and their choice in the knowledge of the objective function, principles of design objective function. Visualization and transfer minima search to finding maxima and vice versa. Explain the concept of misleading function. Explain the concept of complexity of the problem, classification according to the "level" of complexity, explain what the limits of computing technologies exist (Bremermann’s limit, ...). What are the permutation test problems, give examples. Define a multi-purpose optimization Explain the concept of Pareto set, what is the Pareto frontier. Give examples for borders: min-min, max-min, max-min, max-max problem. Explain the concept of local Pareto frontier. Explain the concept of dominant and subdominant solutions, give an example. What is the relation must be the individual components of the objective function to the Pareto set was / was not the point. Example of objective function for multi-purpose optimization.
4. Restrictions on the utility function - problem formulation. Restrictions on individual parameters - parameters during treatment leaving a space of possible solutions. Types of penalties and jejch impact on the geometry of the objective function and its continuity. Using real, integer and discrete parameters of the individual. Technology DSH.
5. Formulate and explain the principle algorithms depth-first search, best-first search, greedy algorithm. Formalise mathematical notation, a description of the algorithm in pseudo-code. Provide control and stop the algorithm parameters.
6. Formulate and explain the principle of local search algorithm method, blind algorithm, climbing algorithm, simulated annealing. The difference between these algorithms. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. Provide control and stop the algorithm parameters. Selected stochastic algorithms with evolutionary elements: Formulate and explain the principle of simulated annealing algorithm with elitism and tabu search. The difference between these algorithms. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. Provide control and stop the algorithm parameters.
7. Formulate and explain the principle of genetic algorithm. Terminology GA. Principle of operation, operators GA. Explain the concept of "schemes". Hybrid GA, messy GA, GA parallel, migration and diffusion model. The difference between the versions of the GA. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. How are mutations, roulette selection. Provide control and stop the algorithm parameters.
8. Formulate and explain the principle of evolutionary strategies. Describe the pseudo two-member EC: (1 + 1) -ES, multi-ES (μ + λ) -ES and (μ, λ) -ES, ES recombination (recombination mechanisms) and Adaptive ES (how the adaptation, specifying the relations) . The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. Provide control and stop the algorithm parameters. Formulate and explain the principle of particle swarm algorithm, scatter search and ant colony optimization. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. Provide control and stop the algorithm parameters. Explain the concept of shoaling algorithm.
9. Formulate and explain the principle of the algorithm SOMA, principles and strategies used algorithm: ATO, ATR, ATA and vacancies. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code. SOMA and permutation test problems. Provide control and stop the algorithm parameters. Derive an expression denoting the number of cost function evaluations using different strategies. Formulate and explain the principle of differential evolution algorithm, principle of operation and the used version: DE / best / 1 / exp, DE / rand / 1 / exp, DE / rand-to-best / 1 / exp, DE / best / 2 / exp, DE / rand / 2 / exp, DE / best / 1 / bin, DE / rand / 1 / bin, DE / rand-to-best / 1 / bin, DE / best / 2 / bin, DE / rand / 2 / bin. DE and permutation test problems. Provide control and stop the algorithm parameters. The effect of algorithm parameters on its activities. Describe the selected algorithm in pseudo-code.
10. Explain the principle of genetic programming, grammatical evolution. indicate alternatives: analytical programming, probabilistic incremental program evolution - PIPE, gene expression programming, multiexpression programming and more. Explain the symbolic representation of the solution in the form of a population of individuals. Evolutionary hardware - basic idea.
11. Explain the concept of cellular automaton and complex system. Classify by Wolfram BA, Conway's game of life, examples of modeling by BA. What is artificial life. Basic definitions and existing systems and models. Tierra, biomorf, Sbeat, Sbart, Eden, Galapagos. Selfreproductive machines by Turing and von Neumann. Langton's loop, computer viruses and artificial life (AL). Artificial Life and the edge of chaos (according to Kaufmann) What is the immune system (IS). The principle of IS, IS limits. Explain the concept of swarm intelligence (SI) and identical features and AL. Basic concepts and definitions, representative algorithms SI - particle swarm, scatter search, ant colony optimization, swarm robotic, artificial evolution of complex systems.
12. Explain neural networks (ANN), the basic principle of NS. What is the training set and its use NS. Basic types of networks and their application to different types of problems.
13. Explain what is fractal geometry. Fractal Define basic types of algorithms generating fractals. Explain the concept of fractal dimension, interpolation and compression. How fractals related developmental systems and artificial life. L-systems, turtle graphics, parametric L-systems, L-systems from the perspective of fractal geometry.