Ant colony algorithm

Solo disponible en BuenasTareas
  • Páginas : 4 (858 palabras )
  • Descarga(s) : 0
  • Publicado : 2 de julio de 2010
Leer documento completo
Vista previa del texto
An overview of heuristic solution methods Ants can colour graphs An ant-based algorithm for coloring graphs

Heurística
• El término heurística significa un método con el cuál, basándose en laexperiencia o juicio previos, puede encontrar una solución razonable a un problema dado, pero que no puede garantizar el llegar a una solución matemática óptima

Esquema de soluciones

AssignmentType Problems
• Dados n elementos y m recursos, el problema es determinar una asignación de los elementos a los recursos, optimizando una función objetivo dada y satisfaciendo un conjunto con susrespectivas limitantes.

donde: si el i-ésimo elemento está asignado al recurso j en otro caso es el conjunto de recursos admisibles para el elemento i Sin pérdida de generalidad, la restricción parala función de minimización es:

Q-colouring
La q-coloración de una gráfica G=(V,E) con un conjunto de vértices V={v1,…,vn} y un conjunto de aristas E, es un mapeo c: V  {1,2,…,q} tal quec(vi)≠c(vj) siempre que E contenga una arista [vi,vj] que una a vi y vj. El mínimo número de colores q para el cual exista una q-coloración es llamado el número cromático de G, y es denotado por χ(G). Unacoloración óptima es aquella que usa exactamente χ(G) colores.

Ahora, para formular matemáticamente en términos de ATP: Los elementos son los vértices de V y los recursos son los colores. Desde quesiempre es posible colorear cualquier gráfica G=(V,E) en n=|V| colores, hacemos m=n. si el vértice i recibe sólo un color j en otro caso

donde:

si z>0 en otro caso

La función objetivo f(x)agrega los números asociados con los colores utilizados en el coloreado x. Entonces una coloración óptima utiliza necesariamente todos los colores consecutivos entre 1 y χ(G). Las limitantes Gj(x) evitanaristas que tengan el mismo color en sus puntos finales. Ahora se introducirá la formalización del algoritmo hormiga para atacar un problema ATP.

An ant algorithm for ATP
Para diseñar una...
tracking img