Ant colony algorithm
Páginas: 4 (858 palabras)
Publicado: 2 de julio de 2010
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...
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...
Leer documento completo
Regístrate para leer el documento completo.