Introduction
This post introduces the basic concepts behind Genetic Algorithms with an implementation in Scala. Scala is a type checked, object oriented and functional programming language built on top of Java Virtual Machine. We can leverage Scala's lambdas, partial functions and closures to implement the computational workflow of evolutionary algorithm.
The second part of the implementation of genetic algorithm in Scala introduces the concept and implementation of genetic operations (cross-over, mutation and selection) on a population of chromosomes. Genetic Algorithms II: Operators
The 3rd and final post on genetic algorithms, explores the application of genetic algorithm as a solver or optimizer Genetic Algorithms III: Solver
Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted
Theory
In computer science, Genetic Algorithms are a way of solving problems by mimicking nature. They use the same combination of selection, recombination and mutation to evolve a set of candidates for resolving a given problem. The basic computational sequence is
Select the initial population (search space) as a set of chromosones which represent candidates for solving a problem. Encode the chromosones into a vector of real values (continuous process) X(x1,..,xn) or string of bits (00101110101111010111). Evaluate or rank the chromosones using a fitness function .Select the fittest chromosones (which meet the minimum fitness criteria) for reproduction. Pair chromosones for cross-over. The process consists of applying a cross-over rate to interchange fragment or section of the "parent" chromosones from a random point in the encoded string or vector. Mutate chromosomes by flipping one or more of their elements(bits) using a randomly generated index bounded by a mutation rate. Iterate the reproduction cycle (steps 2 to 6) for the current population.
Selection rate is the random threshold value to reduce the current population of chromosones according to their fitness- Crossover rate is used to compute the index beyond with the elements or bits of two parents chromosones are exchange.
The following parents 10001001110010010 1010001001000011 will generate the following offsprings 10001001110010011 and 1010001001000010 - Mutation Rate is used to compute the index of the element(s) or bit(s) in a chromosome that is/are mutated (or flipped).10001001110010010 becomes 10001001110000010
Chromosomes
The first step is to implement the key components of a genetic algorithm The implementation has to be generic enough to support any kind of fitness functions and encoding scheme.
A chromosomes is composed of one or several genes, each representing a predicate, axiom, fact or a rule/policy.
A Chromosone class wraps a list of parameterized genes, code (genetic code) (line 1). The most important methods related to chromosomes are
A chromosomes is composed of one or several genes, each representing a predicate, axiom, fact or a rule/policy.
A Chromosone class wraps a list of parameterized genes, code (genetic code) (line 1). The most important methods related to chromosomes are
- +- for the cross-over between two chromosomes (line 6)
- ^ for the mutation of each chromosome (line 11)
- /= for the normalization of the fitness value of each chromosome during the selection process (line 14)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | final class Chromosome[T <: Gene](val code: List[T]) { var unfitness: Double = 1000*(1.0 + Random.nextDouble) // cross-over def +- ( that: Chromosome[T], gIdx: GeneticIndices): (Chromosome[T], Chromosome[T])= {} // mutation def ^ (gIdx: GeneticIndices): Chromosome[T] = {} // normalization of fitness def /= (normalizeFactor: Double): Unit = {} ... } |
The class GeneticIndices converts the cross-over and mutation probability (or rate) into indices (or position) on the bits of the chromosome or gene the cross-over and mutation is applied. The parameter chOpIdx defines the index along the bit string of a chromosome and geneOpIdx the index along the bit string of a gene
case class GeneticIndices(chOpIdx: Int, geneOpIdx: Int)
The generic indices are generated from the cross-over or mutation rate (probability) by the method geneticIndices (line 1). The index of the bit for genetic operations on the chromosome is defined as chIdx (ratio over the length of the chromosome) (lines 5 - 8). Likewise, the index or position of the bit genetic operations on the genes is defined as gIdx (line 11)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def geneticIndices(prob: Double): GeneticIndices = { var idx = (prob*chromosomeSize).floor.toInt val chIdx = if(idx == chromosomeSize) chromosomeSize-1 else idx idx = (prob*geneSize).floor.toInt val gIdx = if(idx == geneSize) geneSize-1 else idx GeneticIndices(chIdx, gIdx) } |
Genes
The class Gene wraps the genetic code associated to a predicate or a rule and takes four parameters:
- id: This is the identifier of the gene. It is usually the name of the variable represented by the gene (line 2).
- target: This is the target value or threshold to be converted or discretized into a bit string (line 3).
- op: This is the operator that is applied to the target value (line 4).
- discr: This is the discretization (or quantization) scheme that converts a numerical (real) value to an integer which is then converted into bits. It also supports the conversion of the bits string back to a numerical value.
1 2 3 4 5 6 7 8 9 10 11 12 | class Gene( val id: String, target: Double, op: Operator)(implicit discr: Discretization) { val bits: Bitset def +- (that: Gene, gIdx: GeneticIndices): Gene = {} def ^ (gIdx: GeneticIndices): Gene = ^ (gIdx.geneOpIdx) def ^ (idx: Int): Gene = {} def decode(bits: BitSet): (Double, Operator) { } } |
Quantization
The class Discretization has two arguments
- A function, toInt, converts a real value to an integer (line 2)
- A reverse function toDouble converts the integer back to a real value (line 3)
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Discretization( toInt: Double => Int, toDouble: Int => Double) { def this(R: Int) = this( (x: Double) => (x*R).floor.toInt, (n: Int) => n/R ) } def decode(bits: BitSet): (Double, Operator) = (discr.toDouble(convert(geneBits.rValue, bits)), op(convert(geneBits.rOp, bits)) ) |
The instantiation of Gene (lines 5-6) converts a predicate into a bit string
of type java.util.BitSet. The bit string is decoded by the decode method of the Gene companion object (lines 10 - 12).
Genetic population
The Population class takes two parameters:
select for the selection of the fittest chromosomes of the population (line 8)
+- for the pair-wise crossover of all the chromosomes (line 1)
^ for the mutation of each chromosome (line 12).
- limit: This is the maximum size of the population (line 4)
- chromosomes: This is the pool of chromosomes defining the current population (line 5).
select for the selection of the fittest chromosomes of the population (line 8)
+- for the pair-wise crossover of all the chromosomes (line 1)
^ for the mutation of each chromosome (line 12).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | type Pool[T <: Gene] = ArrayBuffer[Chromosome[T]] class Population[T <: Gene]( limit: Int, val chromosomes: Pool[T]) { // selection operator def select(score: Chromosome[T] => Unit, cutOff: Double) // cross-over operator def +- (xOver: Double) // mutation operator def ^ (mu: Double) // ... } |
This completes the first part of the implementation of genetic algorithms in Scala. The next post dives into the details in the implementation of the genetic operators.
References
- Tutorial Darell Whitley - Colorado State University
- Short Tutorial from University of California, Davis
- Genetic Algorithms in Search, Optimization & Machine Learning D. Goldberg Addison-Wesley
- Programming in Scala M. Odersky, L. Spoon, B. Venners - Artima 2010
- Scala for Machine Learning - Patrick Nicolas - Packt Publishing
Great and useful article. Creating content regularly is very tough. Your points are motivated me to move on.
ReplyDeleteSEO Company in Chennai
What's more, organizations need to perceive and profit by the open doors these advancements present. machine learning course
ReplyDeleteGreat Article
ReplyDeletefinal year projects on machine learning
Final Year Project Centers in Chennai
JavaScript Training in Chennai
JavaScript Training in Chennai
Дамская сумочка это настоящий предмет искусства. Мануфактурщики постоянно экперементируют с текстурой, а также материалом, создавая невероятные шедевры из разных кож. И конечно вместе с этими необычными остаются постоянно популярными классические сумки из кожи, крутые и подкупающие своей элегантностью и высоким стилем. Настоящая свиная кожа, идеальная фурнитура, опыт и влияние новых стилей итальянской моды вдохновляют работников летние сумки на производство самых крутых женских сумочек. Последним откровением оказалась квадратная кожаная сумка. Украшенная аккуратными квадратами из золотых клепок, - она станет блистательным дополнением твоего имиджа. Попуупайте белую, для того, чтобы бысть стильной и заслужить восторженные взоры.
ReplyDeleteIt will be an easy matter for you to bring your laptop to your workshop at home when you need to perform experiments. artificial intelligence course in hyderabad
ReplyDeleteThis is my first visit to your blog! We are a team of volunteers and new
ReplyDeleteinitiatives in the same niche. Blog gave us useful information to work. You
have done an amazing job!
artificial intelligence training in Bangalore
Невероятно волшебные, а также невероятно точнейшие интернет гадания для предсказания своего ближайшего будущего - это непременно то, что увидит вас на страницах нашего сайта. Гадание выйду ли замуж является самым доступным и легким способом для извлечения важных знаний из эмпирического поля земли.
ReplyDeleteНевероятно познавательные и невероятно правдивые онлайн гадания для предречения вашего ближайшего будущего, это исключительно то, с чем вы познакомитесь на нашем портале. Самые точные гадания таро онлайн является самым доступным и простым вариантом для получения нужных сведений из информационного поля земли.
ReplyDeleteРуны гадание что происходит дает угадать, что вас ожидает в предстоящем времени. Попытка увидеть предстоящие действия постоянно зачаровывал людей. Всякий жаждет предугадать собственное будущее и воспринимает конкретные средства ворожбы наиболее действенными.
ReplyDeleteМногочисленное число развлекательных программ анонсируется ежемесячно. Особо популярным вариантом достать ожидаемую игрушку является скачать старые слабые игры. Понимать толк в поджанрах ПС игрушек не особо легко из-за огромного их многообразия. Загружая игрушки с интернет-сервера вы получите максимальный уровень защищенности. Обманщики сумеют использовать неопытность юзеров и продавать спам-программы. Скачивание Torrent является простейшей процедурой, терпимой даже для юных пользователей.
ReplyDeleteYour blog is very exciting. I read them so much that I was even late for work. I recommend visiting my site https://youtube-to-mp3-converter.com/. This is a Youtube 2 mp3 Converter that lets you download music to your iPhone or computer.
ReplyDeleteБесчисленное изобилие игрушек издается ежемесячно. Максимально простым вариантом взять ожидаемую игру является https://games9.ru/load/uzhasy/. Знать что к чему в системах компьютерных игрушек не особо легко по причине большого их числа. Загружая игры с интернета вы получите пиковый уровень атаке вирусов. Жулики попробуют использовать непосредственность заказчиков и распределять спам-программы. Закачка торрента представляется простой процедурой, доступной даже для начинающих клиентов.
ReplyDeleteНепосредственно новинки нынешнего времени в невероятно высоком качестве. На сайте мп3смак.ру в наличии все что желаете – скачать песни бесплатно хорошие русский. Какую угодно музыку, расположенную на данной платформе, разрешается слушать вполне на шару. mp3smak.ru – это единственный песенный сайт, который поможет обнаружить нужное в считанные секунды. Найдите новейшую подборку для дороги в транспорте или домашней вечеринки. На земле есть великое множество музыки на любой смак.
ReplyDeleteВспоминает ли меня, гадание считается самым верным способом нагадать будущее человека. Синоптические происшествия или ритуальные убийства животных по прошествии длительного времени основали точное объяснение обнаруженного. Основные варианты ворожбы образовались тысячелетия тому назад до Н.Э.
ReplyDeleteМогут быть оформлены доставки емкостей для раздельного сбора отходов. Все же, на официальном онлайн-магазине фирмы Snab Top посетители имеют возможность при этом оформить здесь https://snabtop.ru/category/betonnye-tsvetochnitsy/. На складе лежат также варианты контейнеров для твердых бытовых отходов из полиматериалов.
ReplyDeleteIf you don"t mind proceed with this extraordinary work and I anticipate a greater amount of your magnificent blog entries
ReplyDeleteBest Data Science Courses in Hyderabad
Различные варианты предсказания судьбы обозначаются как эзотерика. Всякий вид хиромантии эксклюзивный и предназначается для разного рода задач. Гадание на бывшего мужа вернется или нет и когда и верность гаданий прямолинейно зависит от опыта человека. Всякий жаждет просмотреть собственное грядущее и считает конкретные способы ворожбы более эффективными.
ReplyDeleteСтоит отметить, что ресурс казино х казино онлайн официальный начисляет своим гемблерам специальные вознаграждения. Верифицируйтесь на сайте и увидите приятные вознаграждения в своей учетке. Вспомогательный счет поможет загрести немало денежных средств.
ReplyDeleteКазино х – воспользуйтесь преимуществом безопасной игры и заработайте существенные денежные средства. Интернет-игры приобрели существенную распространенность на любом континенте. Развитие текущих процессов позволило игральным порталам основательно развить главные услуги.
ReplyDeleteТолько лишь на странице mr bit регистрация пользователи запросто разыщут подходящую онлайн-игру для отдыха. Посещая компьютерный клуб, игрок имеет возможность погрузиться в увлекательные приключения. Отрываться в компании друзей значительно веселее, чем одному в своем доме.
ReplyDeleteОбилие людей, использующих ЖД транспорт для дальних поездок увеличивается с каждым годом. Передвигаться поездом довольно просто, выгодно и быстро. Не в теме, где купить жд билеты Благовещенск Владивосток - используйте актуальный сайт по заказу билетов на поезд в любом направлении 1poezd.ru.
ReplyDeleteНиже рассмотрены наиболее важные плюсы коммуникации с данной фирмой. Широкий выбор строительных принадлежностей для сферы жилстроя. Получайте максимальные преимущества исключительно тут https://snabtop.ru/category/metallicheskie-kontejnery/.
ReplyDeleteКафель ibero mediterranea изготавливают в огромном количестве, и всякая контора хочет запустить собственный неповторимый дизайн. Невероятный ассортимент узоров и размеров. Ценовой диапазон керамики соответственно отличается.
ReplyDelete