Optimization Algorithms - 21 August 2011 - BioInformatics Pakistan
Thursday, 2016-12-08, 3:08 AM
Welcome Guest | RSS

Login form

Statistics
Total online: 1
Guests: 1
Users: 0

Is Online User
Site Search
Main » 2011 » August » 21 » Optimization Algorithms
11:15 PM
Optimization Algorithms


Optimization Algorithms

1. Description:
   An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values. An algorithm terminates in a finite number of steps with a solution.

   An algorithm is a special case of an iterative method, which generally need not converge in a finite number of steps. Instead, an iterative method produces a sequence of iterates from which some subsequence converges to a solution.

   Many authors use "algorithm" more broadly for both finitely terminating algorithms and for iterative methods.

2. Conceptual Algorithm:

3. Introduction:

  1. Inspired by natural evolution
  2. Population of individuals
    • Individual is feasible solution to problem
  3. Each individual is characterized by a Fitness function
    • Higher fitness is better solution
  4. Based on their fitness, parents are selected to reproduce offspring for a new generation
    • Fitter individuals have more chance to reproduce
    • New generation has same size as old generation; old generation dies
  5. Offspring has combination of properties of two parents
  6. If well designed, population will converge to optimal solution
  7. Pseudocode
  8. Example Of Convergence
  9. Reproduction mechanisms have no knowledge of the problem to be solved
  10. Link between genetic algorithm and problem:
    • Coding
    • Fitness function
4. Basic Principles:
  1. Coding or Representation
    • String with all parameters
  2. Fitness function
    • Parent selection
  3. Reproduction
    • Crossover
    • Mutation
  4. Convergence
    • When to stop
  • An individual is characterized by a set of parameters: Genes
  • The genes are joined into a string: Chromosome
  • The chromosome forms the genotype
  • The genotype contains all information to construct an organism: the phenotype
  • Reproduction is a "dumb” process on the chromosome of the genotype
  • Fitness is measured in the real world (‘struggle for life’) of the phenotype
5. Coding
  1. Parameters of the solution (genes) are concatenated to form a string (chromosome)
  2. All kind of alphabets can be used for a chromosome (numbers, characters), but generally a binary alphabet is used
  3. Order of genes on chromosome can be important
  4. Generally many different codings for the parameters of a solution are possible
  5. Good coding is probably the most important factor for the performance of a GA
  6. In many cases many possible chromosomes do not code for feasible solutions

Category: Algorithms | Views: 479 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Tag Board
200
Your Ads
Site friends

Copyright MyCorp © 2016
Free website builderuCoz