Programación y simulación de un sistema inteligente a través de algoritmos genéticos

González López, Alberto (2018). Programación y simulación de un sistema inteligente a través de algoritmos genéticos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: Programación y simulación de un sistema inteligente a través de algoritmos genéticos
Author/s:
  • González López, Alberto
Contributor/s:
  • Sánchez Couso, José Ramón
Item Type: Final Project
Degree: Grado en Ingeniería de Computadores
Date: 2018
Subjects:
Freetext Keywords: Instrumentación virtual
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (3MB)
[img] Archive (ZIP) (Anexos) - Users in campus UPM only
Download (3MB)

Abstract

El presente proyecto titulado “Programación y simulación de un sistema inteligente a través de algoritmos genéticos” tiene como finalidad programar y simular a través de un motor gráfico, en este caso Unity, para mostrar la capacidad de los algoritmos genéticos al desarrollar un sistema inteligente que se adapte a un entorno específico. El problema planteado consiste en un entorno virtual en el que un depredador tiene como objetivo capturar a sus presas. La solución del problema por parte de las presas pasa por desarrollar sus capacidades motoras a través de la programación evolutiva, para así adaptarse cada vez mejor con cada nueva generación, como en la evolución biológica, hasta que al depredador no le sea posible capturar a dichas presas, momento en el que obtendremos la “población solución”. A través del algoritmo genético simple iremos generando las distintas poblaciones de presas. La población inicial empezará con valores completamente aleatorios y dado su fitness -el valor o característica a mejorar en generaciones posteriores- iremos generando la descendencia, a través de la selección, la herencia y la mutación genética. La selección de los candidatos a los que se les extraerán los valores hereditarios con los que conformaremos la siguiente generación, parte de un criterio propio; en esta ocasión consistirá en escoger un valor fijo de porcentaje de los individuos más aptos de cada población. Con dichos candidatos conformaremos a los individuos progenitores, a partir de los cuales se creará la siguiente generación que adquirirá sus genes de forma aleatoria entre un progenitor u otro; es decir, se configurará la herencia genética adquirida. Posteriormente, todos los individuos de las sucesivas generaciones tendrán posibilidades de sufrir una mutación genética. De esta forma, se escogerá para este proyecto un parámetro que indique el porcentaje de posibilidades de padecer algún tipo de mutación genética, lo que conllevará a sus descendientes a adquirir valores aleatorios en sus genes. Es muy importante que tengamos en cuenta este aspecto en concreto, en lo que respecta a la evolución biológica, ya que las mutaciones constituyen la base de la evolución. El impacto de la mutación solo adquiere una visibilidad notoria en la evolución cuando una nueva versión de un gen que originalmente surge por mutación aumenta su frecuencia y se extiende a toda la población gracias a la selección natural. La selección natural actúa incrementando la frecuencia de las mutaciones genéticas que son más ventajosas. Por ello, los individuos que han sufrido mutaciones ventajosas son los que tienen más posibilidades de sobrevivir y, por tanto, de reproducirse, transmitiendo sus genes a su descendencia. Se producen, así, los saltos evolutivos generacionales. Esta actuación producida por la selección natural se desarrollará a lo largo de este proyecto de acuerdo con el algoritmo, hasta el momento en el que se alcance el valor máximo de iteraciones o se cumpla un criterio de parada. Por último, el criterio de parada va a consistir en alcanzar la “población solución”; es decir, la población en la que todos los individuos de la misma generación obtendrán valores de tiempo máximos en los que puedan permanecer vivos. En ese momento habremos conseguido que todos y cada uno de los calamares de esa generación hayan sobrevivido al tiburón, por lo que se habrán adaptado al entorno y habrán evolucionado para sobrevivir, tal y como sucede en la naturaleza. Abstract: This Project, whose title is “Programming and simulation of an intelligent system through genetic algorithms”, has as aim programming and simulating in a cross-platform game engine, in this case Unity, to show the capacity of genetic algorithms of developing an intelligent system able to adapt to a specific environment. The suggested problem consists of a virtual environment in which a predator has the objective of capturing its preys. The preys’ solution to this problem is developing their motor abilities through evolutionary programming, thus in every generation they will adapt better and better, like in biological development. The solution will be obtained in the moment when the predator is not able to capture the preys. The different populations of preys will be created through the simple genetic algorithm. The initial population will start having random values and taking into account its fitness, the value or characteristics to be improved in the following generations, offspring will be created thanks to the selection, inheritance and genetic mutation. The selection of the candidates, of which the inherited values will be taken to form the following generation, has as basis the criterion of choosing a thirty percent of the most suitable individuals of each population. From the candidates previously mentioned the ancestor individuals will form, from which the following generation will be created; obtaining their genes and the hereditary information, randomly retrieved between ancestors, what will form the genetic acquired inheritance. Later, all individuals from consecutive generations will have the chance of suffering genetic mutation; choosing in this project a percent of possibilities of suffering any type of genetic mutation, what will imply their offspring to acquire random values in their genes. It is of utmost importance to bear in mind this aspect in biological development, since mutations are the basis of development. The repercussion of mutation will be relevant in development when a new version of a gene, originally formed by mutation, increases its frequency and spreads through all the population thanks to natural selection. Natural selection acts increasing the frequency of those genetic mutations that are more advantageous. Therefore, individuals that had suffered advantageous mutations are those with a higher chance to survive and, thereby, to reproduce, transmitting their genes to their offspring and, hence, producing leaps in evolutionary generations. The behavior produced in natural selection, will be reproduced throughout this project successively according to the algorithm, up to the moment when the highest value of iterations is reached or they fulfil a moment of stop. In this case, the moment of stop will consist in reaching the solution population, that is to say, the population in which all individuals of the same generation obtain maximum time values in which they can remain alive. It will be in that moment when we would have accomplished the objective, programming and simulating an intelligent system that has adapted to an environment and has developed to survive as is happens in natural world.

More information

Item ID: 51935
DC Identifier: http://oa.upm.es/51935/
OAI Identifier: oai:oa.upm.es:51935
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 05 Sep 2018 06:48
Last Modified: 05 Sep 2018 06:48
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM