Genetic Algorithm: Example

117 slides
4.14 MB
604 views

Similar Presentations

Presentation Transcript

1
2

What Do the Following 3 Things Have in Common?

3

Genetic Algorithms (GAs)GAs design jet engines. GAs draw criminals. GAs program computers.

4

A Potpourri of ApplicationsGeneral Electric’s Engineous (generalized engineering optimization). Face space (criminology). Genetic programming (machine learning).

5

Gas Turbine DesignJet engine design at General Electric (Powell, Tong, & Skolkick, 1989) Coarse optimization - 100 design variables. Hybrid GA + numerical optimization + expert system. Found 2% increase in efficiency. Spending $250K to test in laboratory. Boeing 777 design based on these results.

6

EngineousA new software system called Engineous combines artificial intelligence and numerical methods for the design and optimization of complex aerospace systems. Engineous combines the advanced computational techniques of genetic algorithms, expert systems, and object-oriented programming with the conventional methods of numerical optimization and simulated annealing to create a design optimization environment that can be applied to computational models in various disciplines. Engineous has produced designs with higher predicted performance gains that current manual design processes - on average a 10-to-1 reduction of turnaround time - and has yielded new insights into product design. It has been applied to the aerodynamic preliminary design of an aircraft engine turbine, concurrent aerodynamic and mechanical preliminary design of an aircraft engine turbine blade and disk, a space superconductor generator, a satellite power converter, and a nuclear-powered satellite reactor and shield.*Source: Tong, S.S. ; Powell, D. ; Goel, S. Integration of artificial intelligence and numerical optimization techniques for the design of complex aerospace systems

7

Engineous*Engineous Software, Inc. provides process integration and design optimization software solutions and services. The company's iSIGHT software integrates key steps in the product design process, then automates and executes those steps through design exploration tools like optimization, DOE, and DFSS techniques. The FIPER infrastructure links these processes together in a unified environment. Through FIPER, models, applications and "best" processes are easily shared, accessed, and executed with other engineers, groups, and partners. Engineous operates numerous sales offices in the U.S., as well as wholly owned subsidiaries in Asia and Europe. Customers include leading Global 500 companies such as Canon, General Electric, General Motors, Pratt & Whitney, Honeywell, Lockheed Martin, Toshiba, MHI, Ford Motor Company, Chrysler, Toyota, Nissan, Renault, Hitachi, Peugeot, MTU Aero Engines, TRW, BMW, Rolls Royce, and Johnson Controls, Inc. Additional information may be found at www.Engineous.com and http://components.Engineous.com.

8

Recent news on Engineous*Paris, France, and Providence, R.I., USA, June 17, 2008 – Dassault Systèmes (DS) (Nasdaq: DASTY; Euronext Paris: #13065, DSY.PA), a world leader in 3D and Product Lifecycle Management (PLM) solutions and Engineous Software, a market leader in process automation, integration and optimization, today announced an agreement in which DS would acquire Engineous Software. This acquisition will extend SIMULIA’s leadership in providing Simulation Lifecycle Management solutions on the V6 IP collaboration platform. The proposed acquisition, for an estimated price of 40 million USD, should be completed before the end of July subject to specific closing conditions.Dassault Systèmes to Acquire Engineous Software 06/17/2008http://www.3ds.com/company/news-media/press-releases-detail/release//single/1789/?no_cache=1

9

Criminal-likeness Reconstruction No closed form fitness function (Caldwell & Johnston, 1991). Human witness chooses faces that match best. GA creates new faces from which to choose.

10

What are GAs?GAs are biologically inspired class of algorithms that can be applied to, among other things, the optimization of nonlinear multimodal functions. Solves problems in the same way that nature solves the problem of adapting living organisms to the harsh realities of life in a hostile world: evolution.Let’s watch a video...

11

What is a Genetic Algorithm (GA)?A GA is an adaptation procedure based on the mechanics of natural selection and genetics. GAs have 2 essential components: Survival of the fittest (selection) Variation

12

Nature as Problem SolverBeauty-of-nature argument How Life Learned to Live (Tributsch, 1982, MIT Press) Example: Nature as structural engineer

13

Owl Butterfly

14

Evolutionary is Revolutionary!Street distinction evolutionary vs. revolutionary is false dichotomy. 3.5 Billion years of evolution can’t be wrong. Complexity achieved in short time in nature. Can we solve complex problems as quickly and reliably on a computer?

15

Why Bother?Lots of ways to solve problems: Calculus Hill-climbing Enumeration Operations research: linear, quadratic, nonlinear programming Why bother with biology?

16

Combinatorial Probleme.g. SatisfiabilityIs there a truth assignment to the boolean variables such that every clause is satisfied?http://www.cs.sunysb.edu/~algorith/files/satisfiability.shtml deals with the study of finite or countable discrete structures deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria

17

Non-linear Programming*In the diagram above there are many local minima; that is, points at the bottom of some portion of the graphConsider the following nonlinear program:minimise x(sin(3.14159x)) subject to 0 <= x <= 6nonlinear programming (NLP) is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are nonlinearhttp://people.brunel.ac.uk/~mastjjb/jeb/or/nlp.html

18

Why bother with biology? Robustness = Breadth + Efficiency. Gradient search technique A hypothetical problem spectrum:

19

GAs Not NewJohn Holland at University of Michigan pioneered in the 50s. Other evolutionaries: Fogel, Rechenberg, Schwefel. Back to the cybernetics movement and early computers. Reborn in the 70s.Professor of Psychology and Electrical Engineering & Computer Science Ph.D. University of Michigan Area: Cognition and Cognitive Neuroscience http://www.lsa.umich.edu/psych/people/directory/profiles/faculty/?uniquename=jholland

20

*Genetic algorithmsVariant of local beam search with sexual recombination.

21

*How GAs are different from traditional methods?GAs work with a coding of the parameter set, not the parameter themselves. GAs search from a population of points, not a single point. GAs use payoff (objective function) information, not derivatives or other auxilliary knowledge. GAs use probabilistic transition rules, not deterministic rules.

22

*Traditional ApproachProblem: Maximise the function f(S1, S2, S3, S4, S5) = sin(S1)2 * sin(S2)2+s3 - loge(S3)*S4-S5 Traditional approach: twiddle with the switch parameters.y = f(S1, S2, S3, S4, S5)outputSetting of five switchesS1, S2, S3, S4, S5

23

*Genetic AlgorithmNatural parameter set of the optimisation problem is represented as a finite-length stringoutputSetting of five switchesGA doesn’t need to know the workings of the black box.0f(x)x31S1, S2, S3, S4, S5y = f(S1, S2, S3, S4, S5)Problem: Maximise the function f(S1, S2, S3, S4, S5) = sin(S1)2 * sin(S2)2+s3 - loge(S3)*S4-S5

24

*Main Attractions of Genetic AlgorithmGA Simplicity of operation and power of effectTraditional Optimization Approaches Limitations: continuity, derivative existence, unimodality unconstrained work from a rich database of points simultaneously, climbing many peaks in parallel move gingerly from a single point in the decision space to the next using some transition rule population of strings = points Population of well-adapted diversity

25

GA*maximise 2x1 + x2 - 5loge(x1)sin(x2) subject to x1x2 <= 10  | x1 - x2 | <= 2 0.1 <= x1 <= 5  0.1 <= x2 <= 3Source: Nonlinear Programming, by J E Beasley http://people.brunel.ac.uk/~mastjjb/jeb/or/nlp.html works from a rich database of points simultaneously, climbing many peaks in parallel

26

Browse More Presentations

Last Updated: 8th March 2018

Recommended PPTs