search
Login | Signup | Support
  • 0
  • ×

    genetic algorithm

    by:

    Current Rating : Rate It :

    1909

    Views

    Download
     
    1 : The watermarking of relational databases as a constrained optimization problem , and discuss efficient techniques to handle the constraints Two techniques to solve the formulated optimization problem based on genetic algorithms and pattern search techniques Data partition technique that does not depend on marker tuples to locate The partition and there is resilient to watermark synchronization errors An efficient technique for watermark detection that is based on optimal threshold. The optimal threshold is selected by minimizing probability of decoding error Main contributions of this paper
    2 : When to Use a GA Alternate solutions are too slow or overly complicated Need an exploratory tool to examine new approaches Want to hybridize with an existing solution Benefits of the GA technology meet key problem requirements
    3 : GENETIC ALGORITHM Genetic algorithm is a population-based search method. Genetic algorithms are acknowledged as good solvers for tough problems. An initial population is created consisting of randomly generated rules. Each rule Can be represented by a string of bits. Example: Suppose that samples in a given training set are described by two Boolean attributes A1 and A2 and that there are two classes C1 and C2 The Rule: IF NOT A1 AND NOT A2 THEN C1 This rule can be encoded as “001” Where the two left most bits represents attributes A1 and A2 respectively and rightmost Represents class if an attribute has k values where k>2 then k bits may be used to encode the attribute Values. similarly classes can be encoded Based on the notation of survival of the fittest ,a new population is formed to consist of the Fittest rules in current population
    4 : . WHAT IS A GENETIC AGORITHM ? The general scheme of a GA can be given as follows: begin INITIALIZE population with random candidate solutions; EVALUATE each candidate; repeat SELECT parents; RECOMBINE pairs of parents; MUTATE the resulting children; EVALUATE children; SELECT individuals for the next generation until TERMINATION-CONDITION is satisfied end
    5 : Genetic algorithm is based on the principles of natural selection survival of the fittest Genetic algorithm uses the objective function directly in the search .GA searches the solution space by maintaining a population of potential solution then by using evolving crossover ,mutation and selection GA creates the successive generations of solution that evolve and inherit the positive Characteristics of the parents and thus gradually approach optimal or near optimal solution By using the objective function directly in the search.GA can be effectively applied in nonconvex ,highly nonlinear complex problems GA can be frequently applied to solve optimization problems and nonlinear problems with complicated constraints or non differentiable objective functions
    6 : Components of a GA Encoding technique (gene, chromosome) Initialization procedure (creation) Evaluation function (environment) Selection of parents (reproduction) Genetic operators (mutation, recombination)
    7 : reproduction population evaluation modification discard deleted members parents children evaluated children The GA Cycle
    8 : Chromosomes could be: Bit strings (0101 ... 1100) Real numbers (43.2 -33.1 ... 0.0 89.2) Permutations of element (E11 E3 E7 ... E1 E15) Lists of rules (R1 R2 R3 ... R22 R23) Program elements (genetic programming) ... any data structure ... population Population
    9 : Reproduction Parents are selected at random with selection chances biased in relation to chromosome evaluations. reproduction children population parents
    10 : Modifications are stochastically triggered Operator types are: Mutation Crossover (recombination children modification Modified children Chromosome Modification
    11 : Evaluation evaluation modified children evaluated children The evaluator decodes a chromosome and assigns it a fitness measure The evaluator is the only link between a classical GA and the problem it is solving
    12 : population discard Discard members Deletion Generational GA: entire populations replaced with each iteration Steady-state GA: a few members replaced each generation
    13 : . The feasible set ?i the set of values of ?I that satisfy all the constraints in Gi GA’s do not work directly with the points in the set ?i, but rather with a mapping of points in ?i in to a string of symbols called chromosomes A simple binary representation scheme uses symbols from{0,1};each chromosome is L symbols long. As an example the binary chromosome representing the vector ?i=[?i1…….?in] is indicated below 0101010101010101 1111111111111111 ……….. 0011001100110011 ……………………………….. ……………………………… …………………………….. ?i1 ?i2 ?in each component of ?i uses L/n bits .the chromosome representation automatically handles the interval constraints ?i. Each chromosome has a corresponding values of the objective function ,referred to as the fitness of chromosome To handle the other type of the constraints we penalize the infeasible chromosomes by Reducing their fitness value according to a penalty function f(?i),which represents the degree of infeasibility
    14 : If we are solving the maximization problems with constraints Gi={gi1…….gip}, then fitness function is used is fc (Si+ ?i)+?f(?i) Where ??R? is the penalty multiplier and is chosen large enough to penalize the objective function in case of infeasible ?i. Penality function is given by: f(?i)=? gij?(?i)
    :

    Presentation Tags

    Copyright © 2019 www.slideworld.com. All rights reserved.