Saturday, April 19, 2014

Genetic Algorithm I: Elements

This post is the first section on the implementation of Genetic algorithms in Scala: Basic components
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
Genetic Algorithms have been invented by John Holland in the 1970s and derived their properties from the theory of evolution of Darwin. A living organism consists of cells which are composed of identical chromosomes. Chromosomes are strings of DNA and serves as a model for the whole organism. A chromosome consist of genes that are blocks of DNA and encodes a specific protein.
Recombination (or crossover) is the first stage of reproduction. Genes from parents generate the whole new chromosome (offspring) that can be mutated. During mutation, one or more elements, also known are individuals of the DNA strand or chromosome is changed. This changes are mainly caused by errors in copying genes from parents. The success of the organism in its life measures its fitness.
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
  1. Select the initial population (search space) as a set of chromosones which represent candidates for solving a problem.
  2. Encode the chromosones into a vector of real values (continuous process)  X(x1,..,xn) or string of bits (00101110101111010111).
  3. Evaluate or rank the chromosones using a fitness function. 
  4. Select the fittest chromosones (which meet the minimum fitness criteria) for reproduction.
  5. 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. 
  6. Mutate chromosomes by flipping one or more of their elements(bits) using a randomly generated index bounded by a mutation rate.
  7. Iterate the reproduction cycle (steps 2 to 6) for the current population.
Each of the genetic operators (selection, cross-over and mutation) relies on a parameter:
  • 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
  • +- 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)
This implementation uses the unfitness value of the chromosome for ranking, instead the usual fitness value. It is defined as 1- normalized_fitness (line 3).

 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.
The genes as subjected to the same genetic operations as the chromosomes: cross-over (line 8) and mutation (line 9). The conversion from bits string back to numerical value is implemented by the method deconde (line 11).

 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)
The main benefit to encapsulate the two conversions into a single class is to reduce the risk of inconsistency and inaccuracy between these two conversions.

 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:
  • limit: This is the maximum size of the population (line 4)
  • chromosomes: This is the pool of chromosomes defining the current population (line 5).
A reproduction cycle executes the following sequence of three genetic operators on a population:
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

44 comments:

  1. Great and useful article. Creating content regularly is very tough. Your points are motivated me to move on.


    SEO Company in Chennai

    ReplyDelete
  2. What's more, organizations need to perceive and profit by the open doors these advancements present. machine learning course

    ReplyDelete
  3. Дамская сумочка это настоящий предмет искусства. Мануфактурщики постоянно экперементируют с текстурой, а также материалом, создавая невероятные шедевры из разных кож. И конечно вместе с этими необычными остаются постоянно популярными классические сумки из кожи, крутые и подкупающие своей элегантностью и высоким стилем. Настоящая свиная кожа, идеальная фурнитура, опыт и влияние новых стилей итальянской моды вдохновляют работников летние сумки на производство самых крутых женских сумочек. Последним откровением оказалась квадратная кожаная сумка. Украшенная аккуратными квадратами из золотых клепок, - она станет блистательным дополнением твоего имиджа. Попуупайте белую, для того, чтобы бысть стильной и заслужить восторженные взоры.

    ReplyDelete
  4. It 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

    ReplyDelete
  5. This is my first visit to your blog! We are a team of volunteers and new
    initiatives in the same niche. Blog gave us useful information to work. You
    have done an amazing job!

    artificial intelligence training in Bangalore

    ReplyDelete
  6. Невероятно волшебные, а также невероятно точнейшие интернет гадания для предсказания своего ближайшего будущего - это непременно то, что увидит вас на страницах нашего сайта. Гадание выйду ли замуж является самым доступным и легким способом для извлечения важных знаний из эмпирического поля земли.

    ReplyDelete
  7. Невероятно познавательные и невероятно правдивые онлайн гадания для предречения вашего ближайшего будущего, это исключительно то, с чем вы познакомитесь на нашем портале. Самые точные гадания таро онлайн является самым доступным и простым вариантом для получения нужных сведений из информационного поля земли.

    ReplyDelete
  8. Руны гадание что происходит дает угадать, что вас ожидает в предстоящем времени. Попытка увидеть предстоящие действия постоянно зачаровывал людей. Всякий жаждет предугадать собственное будущее и воспринимает конкретные средства ворожбы наиболее действенными.

    ReplyDelete
  9. Многочисленное число развлекательных программ анонсируется ежемесячно. Особо популярным вариантом достать ожидаемую игрушку является скачать старые слабые игры. Понимать толк в поджанрах ПС игрушек не особо легко из-за огромного их многообразия. Загружая игрушки с интернет-сервера вы получите максимальный уровень защищенности. Обманщики сумеют использовать неопытность юзеров и продавать спам-программы. Скачивание Torrent является простейшей процедурой, терпимой даже для юных пользователей.

    ReplyDelete
  10. Your 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
  11. Бесчисленное изобилие игрушек издается ежемесячно. Максимально простым вариантом взять ожидаемую игру является https://games9.ru/load/uzhasy/. Знать что к чему в системах компьютерных игрушек не особо легко по причине большого их числа. Загружая игры с интернета вы получите пиковый уровень атаке вирусов. Жулики попробуют использовать непосредственность заказчиков и распределять спам-программы. Закачка торрента представляется простой процедурой, доступной даже для начинающих клиентов.

    ReplyDelete
  12. Непосредственно новинки нынешнего времени в невероятно высоком качестве. На сайте мп3смак.ру в наличии все что желаете – скачать песни бесплатно хорошие русский. Какую угодно музыку, расположенную на данной платформе, разрешается слушать вполне на шару. mp3smak.ru – это единственный песенный сайт, который поможет обнаружить нужное в считанные секунды. Найдите новейшую подборку для дороги в транспорте или домашней вечеринки. На земле есть великое множество музыки на любой смак.

    ReplyDelete
  13. Вспоминает ли меня, гадание считается самым верным способом нагадать будущее человека. Синоптические происшествия или ритуальные убийства животных по прошествии длительного времени основали точное объяснение обнаруженного. Основные варианты ворожбы образовались тысячелетия тому назад до Н.Э.

    ReplyDelete
  14. Могут быть оформлены доставки емкостей для раздельного сбора отходов. Все же, на официальном онлайн-магазине фирмы Snab Top посетители имеют возможность при этом оформить здесь https://snabtop.ru/category/betonnye-tsvetochnitsy/. На складе лежат также варианты контейнеров для твердых бытовых отходов из полиматериалов.

    ReplyDelete
  15. If you don"t mind proceed with this extraordinary work and I anticipate a greater amount of your magnificent blog entries
    Best Data Science Courses in Hyderabad

    ReplyDelete
  16. Различные варианты предсказания судьбы обозначаются как эзотерика. Всякий вид хиромантии эксклюзивный и предназначается для разного рода задач. Гадание на бывшего мужа вернется или нет и когда и верность гаданий прямолинейно зависит от опыта человека. Всякий жаждет просмотреть собственное грядущее и считает конкретные способы ворожбы более эффективными.

    ReplyDelete
  17. Стоит отметить, что ресурс казино х казино онлайн официальный начисляет своим гемблерам специальные вознаграждения. Верифицируйтесь на сайте и увидите приятные вознаграждения в своей учетке. Вспомогательный счет поможет загрести немало денежных средств.

    ReplyDelete
  18. Казино х – воспользуйтесь преимуществом безопасной игры и заработайте существенные денежные средства. Интернет-игры приобрели существенную распространенность на любом континенте. Развитие текущих процессов позволило игральным порталам основательно развить главные услуги.

    ReplyDelete
  19. Только лишь на странице mr bit регистрация пользователи запросто разыщут подходящую онлайн-игру для отдыха. Посещая компьютерный клуб, игрок имеет возможность погрузиться в увлекательные приключения. Отрываться в компании друзей значительно веселее, чем одному в своем доме.

    ReplyDelete
  20. Обилие людей, использующих ЖД транспорт для дальних поездок увеличивается с каждым годом. Передвигаться поездом довольно просто, выгодно и быстро. Не в теме, где купить жд билеты Благовещенск Владивосток - используйте актуальный сайт по заказу билетов на поезд в любом направлении 1poezd.ru.

    ReplyDelete
  21. Ниже рассмотрены наиболее важные плюсы коммуникации с данной фирмой. Широкий выбор строительных принадлежностей для сферы жилстроя. Получайте максимальные преимущества исключительно тут https://snabtop.ru/category/metallicheskie-kontejnery/.

    ReplyDelete
  22. Кафель ibero mediterranea изготавливают в огромном количестве, и всякая контора хочет запустить собственный неповторимый дизайн. Невероятный ассортимент узоров и размеров. Ценовой диапазон керамики соответственно отличается.

    ReplyDelete
  23. Любые методы гадания обозначаются как мистические учения. Конкретный тип гадания неповторим и подготовлен для разных результатов. Гадание совместное будущее и верность ворожения напрямую зависит от умения человека. Каждый стремится подсмотреть собственную судьбу и представляет определенные способы предсказания будущего максимально действенными.

    ReplyDelete
  24. Для распознавания карт Таро применяются специализированные словари. Надо помнить, что результат ворожбы прямиком зависит от верования гадающего. Бессмысленно фривольно относиться к гаданию на картах. Руна гадание на брак выйду ли я замуж в ближайшее время является самым правдивым вариантом определить судьбу личности. Лучшие приемы хиромантии возникли тысячи лет назад до Н.Э. Синоптические происшествия или ритуальные жертвоприношения со временем основали целенаправленное трактование обнаруженного.

    ReplyDelete
  25. Нередко плитку укладывают на стены в ванной. Первоочередной характеристикой керамогранитной плитки считается её удобство в применении. Посетитель сможет купить Легенда Gres http://www.4kquan.com/space-uid-631733.html в необходимом количестве. Универсальное покрытие считается оптимальным материалом отделки стен в коридоре и уборной.

    ReplyDelete
  26. Нередко плитку укладывают на стены в ванной. Первоочередной характеристикой керамогранитной плитки считается её удобство в применении. Посетитель сможет купить Легенда Gres http://www.4kquan.com/space-uid-631733.html в необходимом количестве. Универсальное покрытие считается оптимальным материалом отделки стен в коридоре и уборной.

    ReplyDelete
  27. Первоочередной характеристикой кафельной плитки является её практичность в применении. Нередко керамику кладут на стены в кухне. Практичное покрытие считается оптимальным материалом обработки поверхностей в обеденном помещении и санузле. Посетитель сумеет купить Легенда Gres http://www.businessindependent.co.uk/hbi-community/community-home/22985-ukijug/profile в любом количестве.

    ReplyDelete
  28. Выбор керамики, предложенный в перечне legendagres.ru http://shtat-un.ru/forum/profile.php?mode=viewprofile&u=264218, вправду велик. Выпуском керамической плитки занимаются многочисленные компании в мире. Основными составными частями для производства являются светлая глина и несущественное количество примесей, меняющих цвет и структуру.

    ReplyDelete
  29. Именно модели эскорт услуги максимально позволит возвысить персональный уровень в какой-угодно компании или перед коллегами по работе. Настоящие красавицы составят вам компанию во время похождения на выставку или в период бизнес встречи. Подобрать модель есть возможность на несколько суток или оформить выезд в компании великолепной женщины за границу.

    ReplyDelete
  30. Для оценки карт Таро применяются профессиональные словари. Надо понимать, что результативность гадания непосредственно зависит от доверия человека. Нет смысла опрометчиво относиться к ворожбе на Таро. Онлайн гадание на картах таро на отношения является наиболее практичным действием нагадать будущее человека. Начальные способы предсказания будущего возникли тысячи лет назад до нашей эры. Синоптические происшествия или церемониальные приношения животных в дар создали конкретное толкование обнаруженного.

    ReplyDelete
  31. Для расшифровки карт Таро употребляют профессиональные словари. Стоит понимать, что эффект гадания напрямую зависит от верования человека. Нецелесообразно опрометчиво относиться к предсказанию судьбы на картах. Гадание на его отношение ко мне значится самым практичным действием нагадать грядущее личности. Ранние порядки ворожбы были образованы тысячелетия тому назад до нашей эры. Природные явления или обрядовые приношения животных в дар с течением времени обосновали определенное интерпретацию обнаруженного.

    ReplyDelete
  32. Молодая супруга Константина Ивлева: «Многих волнует брачный договор, и не боюсь ли я в аду сгореть». Источник https://rusevik.ru/news/655655

    ReplyDelete
  33. В интерактивном шоу-руме покупатель может приобрести подходящее оборудование на различный бюджет. https://www.projector24.ru/multimediynye-proektory/, представленные на страницах «Проектор24», – это идеальный выбор, что вы сможете себе подумать! Проекционные установки считаются лучшим аналогом плазме, а также предоставляют немного уникальных преимуществ.

    ReplyDelete
  34. "Бесконечный цикл". Эксперт спрогнозировал политическое будущее в Грузии. Источник https://newstes.ru/2021/02/23/beskonechnyj-cikl-jekspert-sprognoziroval-politicheskoe-buduschee-v-gruzii.html

    ReplyDelete
  35. Ручные сверла имеют достаточно хорошую заточку. Ручным сверлом довольно просто пробивать небольшие цилиндрические пазы. В общем случае сверла для ручной дрели применяют для сквозного пробивания дырок при ремонтных работах. Безусловно, комплект подточенный бур по бетону SDS-PLUS – лучший вариант, проходит к прочным сплавам, как пример, для листового металла.

    ReplyDelete
  36. Например, с древесиной и некоторыми мягкими стройматериалами трудностей не может быть, но сверлить железо максимально сложно. Выполнение пазов в основном необходимо при выполнении производственных процессов. Конечно, при каких-угодно производственных работах нужно будет сделать несколько отверстий. Используйте в хозяйстве сверло DIN1897 – это максимально подходящий вариант сделать паз идеального размера и глубины.

    ReplyDelete
  37. Главный секрет лежит в способе обработки. Запечь вкуснейшую курочку без особенных сложностей на удивление легко https://trebuha.ru/633-kalifornijskij-salat.html. Примените особенный компонент для создания нестандартного вкуса, а именно, замороженный шпинат. Ингредиенты для приготовления курицы дешевые, понадобится лишь филе и совсем чуть-чуть приправы. Понадобится замариновать филе и досыпать подходящих приправ на свой вкус.

    ReplyDelete
  38. Зажарить обалденную курочку без специфических премудростей на удивление легко https://trebuha.ru/546-salat-iz-cukkini.html. Главная причина спрятана в способе обжарки. Положите секретный элемент для приобретения неповторимого вкуса, например, сок лимона. Необходимо предварительно обжарить окорочка и положить специальных пряностей по душе. Припасы для готовки курочки доступные, необходимо лишь мякоть и совсем чуть-чуть пряности.

    ReplyDelete
  39. Мясо курицы – очень известный продукт на текущий момент. Почти на праздничном столе раз плюнуть заметить поджаренную корочку. Смотрите, попался на глаза прикольный рецепт сочных куриных крылышек на портале http://rmapo.ru/index.php?subaction=userinfo&user=yfehiwy. Невероятный аромат и простота приготовления идеального блюда – получить результат возможно благодаря пошаговому рецепту.

    ReplyDelete
  40. Сбалансированный вкус и простой способ готовки вкусного блюда – получить это реально благодаря поэтапному рецепту. К слову, откопал интересный рецепт сытных курячих крылышек на портале http://enjoimuse.free.fr/CrazyEmpire/index.php?file=Members&op=detail&autor=aqovegeho. Куриное мясо – невероятно признанный продукт сегодня. В большинстве случаев на каждом столе можно повстречать зарумяненную курицу.

    ReplyDelete
  41. На портале маркетплейса «МАКСИДЕН» возможно выбрать гладильная доска gimi купить по особенно выгодной стоимости. Максимально элементарный случай – на каждой кухне конечно имеется чайник. Кухонную утварь правильно символически разбить на пару видов – декоративные и практические, для постоянного использования.

    ReplyDelete
  42. Принадлежности для кухни стоит символически поделить на пару категорий – как декорации и используемые на практике, для постоянного использования. Максимально простой случай – на каждой кухне непременно есть чайник. На сайте интернет-магазина Maksiden просто выбрать мантоварка купить в спб для индукционной по преимущественно оптимальной цене.

    ReplyDelete