�ݺ�ߣ

Genetic Algorithms
George Bora
UTCN
December 4, 2013
George Bora (UTCN) Genetic Algorithms December 4, 2013 1 / 20

Computer Science to Evolutionary Computation
Within the vast ﬁeld of computer science under it’s vast array of potential
applications there exists the branch of artiﬁcial intelligence.

Computer Science to Evolutionary Computation
Within the vast field of computer science under it’s vast array of potential
applications there exists the branch of artificial intelligence.
One of the sub-branches of artificial intelligence is evolutionary
computation which seeks to achieve continuous optimization and
combinatorial optimization by incorporating knowledge of natural evolution
processes.

Basic Concepts from Biology
The basic building blocks for evolutionary computation, which have kept
their names from their native science, are as follows:
genes
allele
chromosome
individual
mapping
mutation and crossover
ﬁtness function

Genes
The element from which this method derives it name, as genes are the
basic building blocks of life.

Genes
The element from which this method derives it name, as genes are the
basic building blocks of life.
So too in our search for the solution for various problems, genes are the
basic elements we switch around and juggle with in order to arrive at a
more optimum solution.

Allele
If genes are the basics of the solution in theory, alleles are the values
encoded in genes are the ones we use in practice, when developing
software which uses genetic programming.

Allele
When the time has passed and the solution must effectively be built or
instantiated it is the allele which forms the blue print we go by.

Allele
When the time has passed and the solution must effectively be built or
instantiated it is the allele which forms the blue print we go by.
In the original vision for genetic algorithms there was only 1 allele per
gene, which was a binary value and was stored in a 1 bit, as the ﬁeld
progressed all of those constrictions have been lifted.

Chromosome and Individual
As in nature an animal can not have it’s information encoded in a single
gene, in programming a solution which warrants genetic algorithms is not
simple enough as to be composed on 1 gene.

Chromosomes are the collection of genes, which make up the blueprint
from which we will map our solution and create the individual.

Chromosomes are the collection of genes, which make up the blueprint
from which we will map our solution and create the individual.
If the chromosomes are the blue prints the individual is the ”end product”,
to make an analogy with software engineering, and individual is to a class
what a instance is to a object.

Mapping
The process by which we construct a individual from the chromosome we
have generated is called mapping, it is one of the important elements
(alongside chromosome structure and ﬁtness functions) we must consider
before we implement our design.

Mapping
The process by which we construct a individual from the chromosome we
have generated is called mapping, it is one of the important elements
(alongside chromosome structure and ﬁtness functions) we must consider
before we implement our design. Mapping and it’s complexity is often tied
with how we deﬁne our alleles,genes and chromosome as well as our
genetic operations, a great deal of planning being required in order to
produce the best possible algorithm.

Crossover
Crossover is one of the fundamental operations within the toolbox of
genetic algorithms, and one of the most important methods by which we
can combine existing chromosomes to form new ones in the search for a
ﬁt enough solution.

Crossover
Crossover is one of the fundamental operations within the toolbox of
genetic algorithms, and one of the most important methods by which we
can combine existing chromosomes to form new ones in the search for a
ﬁt enough solution. It involves separating each chromosome which takes
part into two parts, and then recombining parts from the different old
chromosomes to form the new set of chromosomes.

Mutation
Mutation is the changing of the allele of a gene to another one of it’s
possible values.

Mutation
Mutation is the changing of the allele of a gene to another one of it’s
possible values. This operation permits genetic algorithms to potentially
escape from local optimum solutions, a very important characteristic in the
ﬁeld of artiﬁcial intelligence.

Fitness Function
Via crossover and mutation we can create whole populations of
individuals, potential solutions, and so the question arises when do we
stop the evolutionary cycle?

Fitness Function
Via crossover and mutation we can create whole populations of
individuals, potential solutions, and so the question arises when do we
stop the evolutionary cycle? The answer being when we have reached a
certain vicinity of an ideal solution, but for this we need to evaluate how
close is any one individual to satisfying our demands and being the sought
after solution.

Fitness Function II
The implementation of the ﬁtness function changes from one class of
problems to another, standardization being much more difﬁcult than with
genes, and is one of the most time consuming elements of genetic
programming.

Fitness Function II
The implementation of the fitness function changes from one class of
problems to another, standardization being much more difficult than with
genes, and is one of the most time consuming elements of genetic
programming.
Writing the fitness function, which when given a chromosome will return
how fit or close to the ideal it is, is one of the hardest yet essential tasks in
developing a solution with genetic programming as it is the only way to
close the loop and choose a final solution.

Genetic Algorithms vs Genetic Programming
Within this ﬁeld there exist two very different paradigms, genetic
algorithms and genetic programming the most visible difference between
them being the structure of the chromosomes they produce.

Genetic algorithms work with a chromosome which is linear and often ﬁxed
in length, making them ideal for tunning the behavior of various solutions.

Genetic algorithms work with a chromosome which is linear and often ﬁxed
in length, making them ideal for tunning the behavior of various solutions.
Genetic programming instead uses a tree-structured chromosome variable
in size, which allows it to generate the structure of the solution as well as
the behavior.

The problem
The creation of a algorithm which is capable of classifying a target image,
returning information about the general structure, size and color (the
pre-deﬁned classes) of the object present in the image.

The problem
The creation of a algorithm which is capable of classifying a target image,
returning information about the general structure, size and color (the
pre-deﬁned classes) of the object present in the image.
Requirements:
1 the use of genetic computing within the solution
2 as high of a success rate as possible

Image classification
Image recognition, which can be classified as a sub-field of computer
vision, is a field concerned with the identification of objects and entities
within images.

Image classification
Image recognition, which can be classified as a sub-field of computer
vision, is a field concerned with the identification of objects and entities
within images.
Image classification is a classical image recognition problem in which the
task is to assign labels to images based their content or metadata.

The classes
The labels we apply are called classes and for this algorithm we have
deﬁned 3 great families of classes:
form classes: for now we have deﬁned classes for circles,
triangles(isosceles) and circles although additions to these are
relatively easy to add due to our use of genetic algorithms
color classes: right now only red, green and blue are implemented
although using the rgb format is also possible.
size classes: chosen arbitrarily.

The chromosome
The chromosome is fairly simplistic being formed out of:
a gene encoding the form.
a gene encoding the color.
a gene encoding the size.

Genes and Allele
The genes governing shapes at the moment can have the following
values: circle, triangle and square all identiﬁed by numeric codes.

Genes and Allele
values: circle, triangle and square all identiﬁed by numeric codes. The
genes governing color at the moment can accept any color deﬁned by the
SVG standard although they can also handle rgb codes, which would
require 3 separate genes.

Genes and Allele
values: circle, triangle and square all identiﬁed by numeric codes. The
genes governing color at the moment can accept any color deﬁned by the
SVG standard although they can also handle rgb codes, which would
require 3 separate genes.
The genes governing size are again numeric codes which represent hard
coded categories of size.

Mapping
The mapping process is the most intensive one, in terms of time and lines
of code needed, followed closely by calculating the fitness function.
The process consists of:
creating a SVG file from the chromosome requires only the standard
Java standard file API.
converting said .svg file to the .png (raster) format as the image we
are trying to classify will be a raster image, requires calls to the
Inkscape API via Java’s system API.

Fitness function
As the result of the mapping is a image of a similar raster format like the
one we seek to classify, the ﬁtness function simply does a naive
comparison of the two images bit by bit.

Fitness function
As the result of the mapping is a image of a similar raster format like the
one we seek to classify, the ﬁtness function simply does a naive
comparison of the two images bit by bit.
It then normalizes the bit difference to a range between 0 and 1, as
required by the genetic algorithm, this ﬁtness being then used in the
standard manner for deciding which chromosomes pass into the next
generation.

The cons
This procedure has a number of weak points:
genetic algorithms traditionally aren’t suited to image classification.
the speed of this procedure, is very low due to the calls to Inkscape
and the creation of numerous files (can be improved).
the fitness function relies on a very sensible and naive image
comparison method (can be improved).

The pros
A number of points in it’s favour
the available class list, due to the classes being written in SVG, is
very easily extendable.
in it’s current form it requires only Java and Inkscape (a very available
software).
there are a large number of image comparison methods which can be
used for the ﬁtness function.

The End
Thank your for your attention !

The End
Thank your for your attention !
Any questions ?

�ݺ�ߣ

Genetic Algorithms and Image Classification

Recommended

More Related Content

Similar to Genetic Algorithms and Image Classification (20)

Recently uploaded (20)

Genetic Algorithms and Image Classification