DiazRiosJhonnatanSteven2019

Vista previa del material en texto

1 
 
SISTEMA DE VISIÓN ARTIFICIAL PARA LA OPTIMIZACIÓN POR 
ALGORITMO DE COLONIA DE HORMIGAS DE TRAYECTORIAS DE 
TALADRADO DE CIRCUITOS IMPRESOS (PCB) A PARTIR DE 
PROCESAMIENTO DIGITAL DE IMÁGENES 
 
ARTIFICIAL VISION SYSTEM FOR OPTIMIZATION BY ALGORITHM 
ANTS COLONY OF ROUTES OF DRILLING OF PRINTED CIRCUITS 
(PCB) FROM DIGITAL IMAGE PROCESSING 
 
 
Karol Dayan Riaño Tolosa.∗ Jhonnatan Steven Díaz Ríos.** 
 
 
Resumen: En el presente documento se desarrolla un algoritmo bioinspirado en 
colonias de hormigas, usando como base su comportamiento y sistema guía en la 
optimización de desplazamientos, para la mejora de trayectorias de sistemas de 
perforación en circuitos impresos. Mediante el software MATLAB se implementa líneas 
de código basadas en la capacidad de las hormigas de escoger el trayecto de menor 
recorrido mediante la liberación de feromonas. El código define una constante que 
simula una cantidad de hormigas en un camino, una cantidad de feromonas que se 
liberan y diferentes reacciones tomadas por la hormiga definiendo así la mejor 
trayectoria a seguir. Como resultado, a mayor cantidad de hormigas mayor cantidad 
de feromonas y, por consiguiente, mejor resultado a la hora de escoger el camino de 
menor trayectoria de desplazamiento. La relevancia de implementar un código basado 
en un sistema de colonia de hormigas está fundamentada en la reducción de tiempo 
invertido en establecer coordenadas (manualmente) en un programa de perforación, 
así como también su ruta a seguir. 
Palabras clave: ACO, desplazamiento, optimización, procesamiento. 
 
 
 
2 
 
 
Abstract: This paper develops a bioinspirated algorithm in ant colonies, using as a 
base its behavior and guidance system in the optimization of displacements, for the 
improvement of trajectories of perforation systems in printed circuits. Through the 
MATLAB software, lines of code are implemented based on the ability of the ants to 
choose the shortest path through the release of pheromones. The code defines a 
constant that simulates a number of ants in a path, a number of pheromones that are 
released and different reactions taken by the ant, thus defining the best trajectory to 
follow. As a result, the greater the number of ants, the greater the number of 
pheromones and, consequently, the better the result when choosing the path of least 
trajectory. The relevance of implementing a code based on an ant colony system is 
based on the reduction of time spent in establishing coordinates (manually) in a drilling 
program, as well as its route to follow. 
Key Words: ACO, displacement, optimization, processing. 
 
1. Introducción 
En los sistemas de manufactura para ensamble de equipos electrónicos, se requieren 
múltiples operaciones de maquinado. Como es el caso de la perforación de orificios para 
ensamblado de componentes y elementos de sujeción en las tarjetas de circuitos impresos 
PCB [1]. Considerando que cada tarjeta puede tener desde una cantidad unitaria incluso 
llegar hasta miles de orificios se hace indispensable para optimizar la operación de taladrado 
de los PCB determinar la ruta de taladrado óptima para así reducir tiempos de operación. 
Además, en la industria de equipos electrónicos, la operación de perforación de orificios en 
circuitos impresos (PCB) es imprescindible. La creciente variedad de productos que 
necesitan PCB ha conllevado a la aplicación de técnicas de automatización con el fin de 
 
 
3 
 
hacer más competitivos los procesos y optimizarlos. Muchas industrias han adoptado el 
sistema de brazos robóticos y controles numéricos CNC [2] programables en código G, para 
automatizar y gestionar la perforación de orificios en los PCB, debido a su flexibilidad. En 
todos los procesos de mecanizado, el tiempo que gasta el brazo robot de acuerdo a la ruta 
que sigue para posicionar la herramienta de corte y llevar a cabo la operación de mecanizado 
y perforación es un aspecto crítico a ser optimizado. 
 
Con miras en ese objetivo de optimización se va aplicar el algoritmo de colonias de hormigas 
[3] que corresponde a una meta heurística [4] de búsqueda para resolver el problema de 
optimización, en este caso, la ruta de perforación de orificios para componentes en PCB. Así 
mismo, este problema corresponde a un problema de agente viajero [5], simétrico, uni-
objectivo y euclidiano. La presentación del prototipo de captura de imagen, el procesamiento 
de la misma, la ejecución del ACO da la terminación de este proyecto y, al final de este 
documento, se presentan conclusiones del rendimiento y funcionalidad del prototipo como 
también de si se mejora o no con respecto a las perforaciones convencional. 
 
2. Marco Teórico 
2.1. Colonias de Hormigas Naturales y Meta-heurística ACO: 
Las hormigas son insectos sociales que viven en colonias y que, debido a su colaboración 
mutua, son capaces de mostrar comportamientos complejos y realizar tareas complejas 
desde el punto de vista de una hormiga individual [6]. Un aspecto interesante del 
comportamiento de muchas especies de hormigas es su habilidad para encontrar los 
caminos más cortos entre su hormiguero y las fuentes de alimento. Mientras que se mueven 
4 
 
entre estas posiciones, algunas especies de hormigas depositan una sustancia química 
denominada feromona [7]. Si no se encuentra ningún rastro de feromona, las hormigas se 
mueven de manera básicamente aleatoria, pero cuando existe feromona depositada, tienen 
mayor tendencia a seguir el rastro. En la práctica, la elección entre distintos caminos toma 
lugar cuando varios de estos se cruzan. Entonces, las hormigas eligen el camino a seguir 
con una decisión probabilística influida por la cantidad de feromona: cuanto más fuerte es el 
rastro de feromona, mayor es la probabilidad de elegirlo. 
 
En la Figura 1 se ilustra cómo este mecanismo permite a las hormigas encontrar el camino 
más corto: Inicialmente no existe ningún rastro de feromona en el medio y, cuando una 
hormiga llega a una intersección, elige de manera aleatoria una de las bifurcaciones posibles. 
Segundo, según transcurre el tiempo y mientras que las hormigas están recorriendo los 
caminos más prometedores, estos van recibiendo una cantidad superior de feromona. 
Tercero, en el camino más corto habrá un rastro de feromona ligeramente superior y, por lo 
tanto, las decisiones de las siguientes hormigas estarán dirigidas en mayor medida a dicho 
camino. Finalmente, este camino recibirá una proporción mayor de feromona y las hormigas 
optaran por tomarlo. Además, la feromona, evaporable en el tiempo, permite que caminos 
menos prometedores pierdan esta sustancia progresivamente y así no sean escogidos. 
 
Figura 1. Rutas de desplazamiento hormigas. Fuente: Elaboración 
propia. 
 
 
5 
 
 
2.2. Aplicando ACO a Planificación de Trayectorias 
Para nuestro trabajo se identifican � puntos que forman el total de orificios a ser perforados. 
Denotaremos a cada punto por ���, … , ���	
 y la distancia entre estos se identifica como ��
. 
Cada punto se ubica en un plano de dos dimensiones, por ende, dos puntos �� = �� , �� y 
�
 = �
 , �
 tienen una distancia definida por ��
 = ���� − �
�� + ��� − �
��
. 
 
La figura 2 representa el diagrama de flujo para el algoritmo de colonia de hormigas y su 
funcionamiento. Este diagrama nos señala cómo en primera instancia un grupo de hormigas 
ubicadas en una intersección, escogen aleatoriamente una ruta, emprenden un recorrido y 
van depositando feromonas. En segunda instancia, y llegado a otro punto o cruce, las 
hormigas definen si se llegó al final o no; en caso de no ser el final repiten el procedimiento 
de la primera instancia. Cuando las hormigas definen el final de su recorrido pasan a la 
tercera instancia, en la cual, identifican en qué camino hay mayor cantidad de feromona y lo 
toman,depositan nuevamente más feromona y, trascurrido el tiempo la feromona se 
evapora. Finalmente, en la cuarta instancia, se interpreta si el camino recorrido es óptimo o 
no; si no es óptimo se repite la tercera instancia hasta dar lugar a la optimización del camino. 
6 
 
 
 
3. Descripción del proyecto 
En la figura 3 se puede observar el sistema de bloques para el desarrollo del proyecto. 
 
Este sistema de bloques está diseñado para presentar a groso modo el proceso que se 
siguió para lograr el desarrollo del proyecto. Se trabaja sobre dos etapas: el dispositivo de 
captura, definido como el espacio controlado donde se ubica la placa PCB y la cámara que 
toma la foto de esta; y el software de ejecución. El acondicionamiento, procesamiento y 
ajuste de imagen básicamente consisten en que a la imagen capturada se modifique, se 
identifiquen los puntos de perforación y se cree una matriz de almacenamiento donde se 
guarda la posición de los mismos. La ejecución del algoritmo ACO, donde se realiza la 
Figura 2. Diagrama de flujo para el algoritmo ACO. Fuente: 
Elaboración propia. 
 
Figura 3. Diagrama de bloques para la alternativa de solución. Fuente: 
Elaboración propia. 
 
 
7 
 
optimización de trayectos a seguir a partir de los puntos almacenados en la matriz anterior. El 
presentar en gráficos la ruta optima a seguir y una comparativa entre número de 
optimizaciones y distancia recorrida. 
 
4. Puesta en marcha 
En esta sección se mostrará y explicará las diferentes etapas que ha tenido el proyecto en su 
desarrollo de forma más clara y concisa, así como también se verificará cada una de los 
objetivos presentando figuras de cada aspecto. 
 
4.1. Objetivo 1. Captura de imagen de la tarjeta PCB mediante una cámara digital en un 
espacio controlado 
El sistema para la captura de imágenes está ubicado en un espacio controlado definido como 
una caja de dimensiones de 20�� � 20�� � 20��, la cual su cara superior es desplegable de 
forma que se pueda acceder a su interior. Allí se asentará la placa PCB, además, se dispone 
de una webcam de marca “Logitech” y de referencia “c920 HD Pro” la cual será el dispositivo 
de captura de la imagen. Véase la figura 4a para conocer el modelo, diseño y/o estilo de la 
webcam usada en el proyecto. Algunas de las características de este dispositivo son: una 
resolución de captura de 1920�1080 píxeles para mayor nitidez y claridad en la imagen 
capturada; cuenta con una interfaz de conectividad vía USB 3.0 para una mejor velocidad de 
trasmisión de datos, además, esta vía de conexión USB hace que sea mucho más fácil la 
comunicación entre webcam y el software de MATLAB en dónde se procesará la imagen, 
pues la cámara se conectará directamente a la computadora y no habrá necesidad de algún 
8 
 
dispositivo de acople entre estos. En la figura 4b se representa el espacio controlado en 
donde se ubicarán los elementos físicos necesarios, placa PCB y dispositivo de captura. 
 
Antes de continuar, se debe explicar que nuestro código en el software MATLAB es trabajado 
por funciones y cuando una función X es necesitada en alguna otra parte del código es 
llamada y ejecutada allí mismo sin la necesidad de volver a escribir todo el código que esta 
contiene. Es decir, el 100% de código no se podrá encontrar en un solo Script, sino que 
habrá varios, uno para cada función necesaria. Esta división se hace para tener un mejor 
orden del código y así saber qué ejecuta cada línea y ante algún fallo sea fácil de identificar. 
 
4.1.1. Captura de imagen, acondicionamiento y procesamiento 
En primera instancia, desde el software de MATLAB se da la instrucción de tomar la imagen, 
lo que procede a que nuestro dispositivo de captura entre en acción. Ahora, y como se 
mencionó anteriormente, la interfaz de conectividad de la cámara es vía USB (conexión 
directa entre cámara y PC), facilitando en gran manera la transmisión de los datos desde la 
webcam y el software de MATLAB que componen o genera la imagen. El código encargado 
de la captura de la imagen es realmente sencillo, pues solo se necesitan de cinco líneas para 
realizar esta operación. Observe la figura 5. En la quinta línea se crea el canal que conecta la 
cámara con MATLAB, esto es, el lugar por donde los datos serán transmitidos, allí 
 
Figura 4a. Webcam utilizada. Fuente: Elaboración 
propia. 
Figura 4b. Espacio controlado. Fuente: Elaboración 
propia. 
 
 
9 
 
señalamos el puerto en el cual está ubicada la capturadora y la resolución con la cual se 
quiere que se realice la captura. La sexta línea es una línea de configuración de color para 
que la imagen retorne los colores originales de la captura, es decir, en un principio, cuando 
se realizaba una fotografía (independiente de a qué objeto o lugar) la visualización de esta no 
era en una escala de colores “normales” sino que había una sobresaturación del color rojo 
(observe la figura 5a) y este comando nos soluciona dicha situación (observe la figura 5b). La 
séptima línea representa simplemente la variable en donde se guarda la imagen captada. En 
la décima línea, el comando “imwrite(imag,'C:\Users\JONATHAN\Desktop\Grado\01 ACO for 
TSP\imagen.jpg');" es usado para generar y guardar la imagen digital en una locación 
especifica de la computadora y posteriormente poder abrirla como un archivo JPG. 
Finalmente, la undécima línea es una variable en la cual se guarda la imagen generada en la 
línea diez y que será usada en adelante para el desarrollo del ACO. 
 
 
Figura 5. Código para la captura de imagen. Fuente: Elaboración propia. 
10 
 
 
Podemos observar la validación del cumplimiento del primer objetivo en las figuras 6a y 6b. 
La primera presenta el espacio controlado y sus elementos internos necesarios para el 
desarrollo del proyecto; por otro lado, la segunda figura nos muestra la captura de la PCB 
realizada por la cámara digital y que posteriormente será usada para el resto del desarrollo 
del proyecto. 
 
 
4.2. Objetivo 2. Implementar algoritmo de procesamiento digital de imágenes que 
definan posición de orificios 
Una vez obtenida la captura, se realizan dos pasos. Uno para el procesamiento de la imagen 
y otro para definir posiciones y distancias entre los puntos. En el procesamiento de imagen 
nuestro algoritmo, como se observa en la figura 7a, toma la variable donde esta guardada la 
captura y la vuelve a almacenar pero esta vez en dos variables distintas que se modificarán 
 
 
Figura 6a. Validación del espacio controlado. Fuente: 
Elaboración propia. 
Figura 6b. Validación de la captura de imagen. Fuente: 
Elaboración propia. 
Figura 5a. Imagen con sobresaturación de color rojo. 
Fuente: Elaboración propia. 
Figura 5b. Imagen corregida con el comando “set 
(vidobj, ‘ReturnedColorSpace’, ‘RGB’);”. Fuente: 
Elaboración propia. 
 
 
11 
 
(líneas 18 y 19). Estas modificaciones son el cambio en el tamaño de salida que tendrá la 
imagen, tal como se observa de las líneas 20 a 23. Seguidamente, en las líneas 24 a 26 se 
realiza una conversión a escala de grises de una de las variables que ayudará en la 
identificación de los puntos tal como se muestra en la figura 7b. 
 
Posteriormente, para dar la definición de la posición de los puntos el algoritmo usa la imagen 
modificada en escala de grises (figura 7b). Mediante la línea de código “[c,r] = 
imfindcircles(img,[1 1000],'ObjectPolarity','bright','Sensitivity',0.9)” de la línea 28 se identifica 
el tamaño de los círculos y sus posiciones y las almacena en las variables � = �� y � = �� de 
las líneas 34 y 35 respectivamente y que representan la posición tanto en el eje x como el eje 
y de cada punto, para esto véase la figura 8a. Luego, se resuelve la distancia entre cada 
punto usando una ecuación mencionada anteriormente: ��
 = ���� − �
�� + ��� − �
��
. Este 
algoritmo es una estructura anidada donde se toma la cantidadde puntos ya definidos y 
realiza una iteración para cada uno, en cada iteración el código define la distancia entre un 
punto en específico y todos los demás. En la figura 8b, las líneas 44 a 52 ejecutan la 
estructura anida que definen las distancias, mientras las líneas 54 a 57 definen las variables 
en las cuales se almacena la información sobre cantidad de puntos, posiciones y distancias. 
 
 
Figura 7a. Procesamiento de imagen. Fuente: Elaboración 
propia. 
Figura 7b. Conversión a escala de grises de la captura. 
Fuente: Elaboración propia. 
12 
 
 
De esta forma vemos verificado el cumplimiento del segundo objetivo planteado en el 
proyecto. 
Dentro de nuestro código de MATLAB, el cumplimiento de los objetivos uno y dos y sus 
respectivos algoritmos de ejecución se encuentran un mismo Script, por eso toda esta 
sección está definida como una sola función bajo el nombre de “CreateModel()” donde 
hayamos la captura de imagen, el acondicionamiento de la misma, y la definición de cantidad 
y posición de cada punto a taladrar. 
 
4.3. Objetivo 3. Configurar el algoritmo de optimización por colonia de hormigas para 
trayectorias entre orificios en simulaciones de MATLAB 
Para esta sección se deben estudiar tres puntos, pues la configuración y ejecución del ACO 
está ligado a la implementación de otros dos algoritmos simples. Un algoritmo de selección 
de ruleta y a un algoritmo de definición de ruta. 
 
4.3.1. Algoritmo de selección de ruleta 
El algoritmo de selección de ruleta (Roulette Wheel Selection, en inglés) es un algoritmo que 
da un valor numérico aleatorio a diferentes objetos, en nuestro caso a cada punto a taladrar, 
para así, escoger el orden del desplazamiento por los puntos basados en su valor. Dicho 
 
Figura 8a. Identificación y definición de puntos. Fuente: 
Elaboración propia. 
Figura 8b. Definición distancia entre puntos y posición. 
Fuente: Elaboración propia. 
 
 
13 
 
algoritmo es ejecutado por única vez al inicio de la captura, esto es para dar al ACO un 
sistema inicial que optimizar. Este algoritmo es una función que se ejecuta con el nombre de 
“j=RouletteWheelSelection”. En la figura 9 se muestra las 3 líneas de código que componen 
este algoritmo que acaba de ser explicado. 
 
4.3.2. Algoritmo de definición de ruta 
El algoritmo de definición de ruta (TourLength, en inglés), el cual también es una función 
llamada “L=TourLength”, genera la conexión entre cada punto. La figura 10 muestra el 
algoritmo de definición de ruta. 
 
4.3.3. ACO 
El código principal de toda nuestra investigación, la optimización de trayectorias para 
taladrado basado en las colonias de hormigas, se divide en cinco secciones a estudiar, 
donde la cuarta sección contiene el loop que ejecuta las optimizaciones. La primera sección, 
representada en la figura 11, define el problema. Aquí se llaman las funciones anteriormente 
 
Figura 9. Algoritmo de selección de ruleta. Fuente: Elaboración propia. 
 
Figura 10. Algoritmo de definición de ruta. Fuente: Elaboración propia. 
14 
 
creadas: la línea 7 se encarga de llamar a la función model=CreateModel(); la línea 9 
CostFunction=@(tour) TourLength(tour,model) que ejecuta le definición de la ruta; 
finalmente, línea 11 guarda en una variable la definición de cantidad y posición de puntos 
(nVar=model.n). 
 
La segunda sección determina los parámetros con los cuales el algoritmo es aplicado a la 
optimización. En la figura 12 se visualizan los parámetros iniciales. La variable MaxIt de la 
línea 16 es usada para decretar una cantidad de iteraciones que sirven para ejecutar el 
algoritmo tantas veces como este diga y así hallar la mejor optimización. En la línea 18, la 
variable nAnt delimita la cantidad de hormigas que usaremos para realizar el experimento. La 
cantidad de feromona inicial (es decir, solo para la primera iteración) se define en la línea 22 
mediante la variable tau0 y esta a su vez, se define como una constante dividida entre el 
producto de la cantidad de puntos y la distancia de los mismos. Las variables alpha y beta 
señalan el crecimiento exponencial que tendrá la feromona y el crecimiento exponencial de la 
heurística respectivamente, esto es: parámetros ajustables donde alpha controla la 
probabilidad de escoger el punto más cercano sin tener en cuenta el conocimiento otorgado 
por las demás hormigas según las feromonas; por otro lado, beta controla la posibilidad de 
que la hormiga se guie únicamente por la feromonas y deje a un lado el instinto de descubrir 
nuevos trayectos. Finalmente, en la línea 27 la variable rho define la tasa de evaporización 
de la feromona pues es necesario que en el avance del tiempo la feromona se desvanezca 
 
Figura 11. Llamado de funciones para definir el problema. Fuente: Elaboración 
propia. 
 
 
15 
 
para así definir rutas que contienen harta y nula concentración de feromona y así escoger el 
mejor camino. 
 
Para la tercera sección se realiza la iniciación de todas las matrices en donde se guardará 
toda la información generada en cada iteración del programa. Se hallan cuatro matrices, tal 
como se muestra en la figura 13. La matriz de información heurística nombrada 
eta=1./model.D en la línea 32 es un arreglo que guarda las distancias entre los puntos a 
medida que se adquiere conocimiento por parte de las hormigas mediante la exploración. Es 
decir, luego de haber definido cantidad de puntos, posiciones de los mismos y distancias a 
través del segundo objetivo, las hormigas viajarán por un camino por intuición y no por un 
ruta ya trazada y esto luego lo compararán con rutas trazadas. En la línea 34, la matriz de 
feromona tau=tau0*ones(nVar,nVar) presenta el almacenamiento de la cantidad de feromona 
segregada, esto es, que tanta feromona esparcirán las hormigas en cada paso por un 
camino. Finalmente, la línea 46 es una variable que almacena la información de que ruta 
seguida ha sido la mejor solución. 
 
Figura 12. Parámetros iniciales para la ejecución del programa por primera vez. Fuente: 
Elaboración propia. 
16 
 
 
En el loop del ACO de la cuarta sección es donde relacionamos todas las funciones creadas 
y los parámetros determinados. En primera instancia, se ejecuta un ciclo que dura según el 
parámetro MaxIt. Seguidamente se procede a hacer el movimiento de las hormigas una a 
una tal como se observa en la línea 54 de la figura 14. Además, Las líneas de código más 
relevantes de la figura 14 son: la línea 68 que es la selección de ruleta realizando el primer 
valor aleatorio de los puntos identificados para trazar la primera ruta sobre la cual las 
hormigas se moverán. De ahí en adelante, y para cada iteración, las hormigas se 
desplazarán según la función tour (línea 56 y línea 60) y, comparando el recorrido de una 
hormiga con la trayectoria anterior, se define la mejor solución (líneas 76 y 77). La línea 74 
indica el valor del mejor desplazamiento encontrado. 
 
 
Figura 13. Inicialización del algoritmo. Fuente: Elaboración propia. 
 
 
Figura 14. Movimiento de las hormigas. Fuente: Elaboración propia. 
 
 
17 
 
Ahora, en la figura 15 se ejecuta el bucle para el esparcimiento de la feromona, donde para 
cada hormiga se libera una cantidad de sustancia. Veamos la línea 85 donde se expresa que 
para cada hormiga que hace un recorrido se crea una matriz que va guardando estos 
desplazamientos. En la línea 94 se puede observar como el esparcimiento de la feromona 
está ligada a la función tour, es decir, según como se mueva la hormiga pero también a la 
constante Q que se define anteriormente. 
 
Así mismo, la línea de código tau=(1-rho)*tau, línea 101 de la figura 16, hará de sistema de 
evaporización que disminuirá la feromona reduciendo trayectorias innecesarias. En la línea 
104 se guardará el valor de la mejor distancia a recorrer. Mientras que en la línea 107, que 
se visualizará en el “CommandWindow” de MATLAB mostrará los resultados de la mejor 
distancia a recorrer junto con la iteración en la cual se da dicho resultado. Ya para las líneas 
de código de la 109 a la 112 se realizará el despliegue de una gráfica que mostrará la 
imagen captura y sobre estas trayectorias que se podrían ser seguidas por las hormigas. 
Todo esto se puede observar en la figura 16. 
 
 
Figura 15. Esparcimiento de la feromona. Fuente: Elaboración propia. 
18 
 
 
Para la última sección se da el despliegue de una gráfica que compara el número de 
iteraciones contra la distancia, en milímetros, de los trayectos optimizados. La figura 17 
presenta los códigos para el despliegue de esta gráfica. 
 
De esta forma, damos por configurado el algoritmo de optimización basado en las colonias 
de hormigas y ejecutado en el software MATLAB, y así el cumplimiento del tercer objetivo; 
además, la presentación de las figuras 18a y 18b dan soporte del cumplimiento de 
trayectorias definidas por el ACO. 
 
Figura 16. Sistema de evaporación y gráfica de trayectoria. Fuente: Elaboración 
propia. 
 
Figura 17. Gráfica de comparación Iteración vs Distancia. Fuente: Elaboración 
propia. 
 
 
19 
 
 
4.4. Objetivo 4. Comparar el algoritmo por colonia de hormigas con rutas de taladrado 
convencionales (CNC) 
Para el desarrollo de este objetivo se realiza la identificación de cada punto que contiene la 
PCB en coordenadas X,Y. Luego, se procede a escribir el código G para la ejecución en 
máquinas CNC. El código CNC es un código secuencial y escrito en su totalidad por la 
persona, por ende, el recorrido que se realiza no es aleatorio sino que sigue un orden ya 
descrito por quien desarrolla en código. Este orden es permanente, por eso si se desea 
cambiar el orden de la ruta, se debe reescribir el código y pensar que coordenadas se desea 
visitar primero. En la figura 19 se muestra la escritura del código G. 
 
Este código básicamente lo que hace es que se define a qué punto se desea que vaya el 
taladro y este recorra la ruta hasta esa coordenada. Según la línea dos del código, que dice: 
 
 
 
Figura 18a. Validación funcionamiento ACO. Fuente: 
Elaboración propia. 
Figura 18b. Gráfica de comparación distancia vs iteración 
en verificación ACO. Fuente: Elaboración propia. 
 
 
Figura 19. Escritura del código G para máquina CNC. Fuente: Elaboración propia. 
20 
 
G00 X6 Y59 Z0, por ejemplo, está diciendo que el taladro se moverá 6 puntos positivos sobre 
el eje X, 59 puntos positivos sobre el eje Y y 0 punto sobre el eje Z. Es decir, se moverá a la 
coordenada (6,59,0) y los puntos representan el valor métrico de los milímetros. 
Ahora, si nos damos cuenta, a diferencia de este formato, el ACO no se ejecuta sobre una 
ruta predefinida por el desarrollador, sino que el propio ACO es un código que presenta una 
ruta totalmente aleatoria y, a medida que se ejecuta, la optimiza generando la ruta aleatoria 
con menor recorrido. En la figura 20a se muestra la ruta seguida por el taladro según el 
código G que se escribió y simuló. 
 
5 Pruebas 
Al ejecutar nuestro algoritmo se observa cómo se abre la imagen usada como plantilla y 
sobre esta se empiezan a trazar diferentes trayectorias que van siendo optimizadas con cada 
iteración, paso de hormigas y evaporación de la feromona. En las figuras 21a y 21b se 
muestra la visualización de trayectorias, además, cada visualización es diferente pues ellas 
corresponden a iteraciones distintas. También, la figura 22 recalca y muestra como las 
hormigas mantienen una trayectoria como “corta” hasta que, en una iteración mayor (más 
recorridos de hormigas y más feromonas en pasos más cortos), la distancia (también 
nombrada como costo en algunas partes) de dicha trayectoria disminuye. 
 
 
Figura 20a. Ruta predefina en el código G. Fuente: 
Elaboración propia. 
Figura 20b. Ruta del código G sobre la PCB. Fuente: 
Elaboración propia. 
 
 
21 
 
 
 
En la figura 23a y figura 23b, con un aumento de 10 hormigas (para un total de 50) y la 
misma cantidad de iteraciones, se puede detallar como el camino a seguir tiende a tener 
menos trayectos que se crucen entre sí como el mostrado en la figura 21a, aunque la 
distancia final también varía. 
 
 
 
 
 
 
 
 
 
Figura 22. Gráfica iteraciones vs costo. Fuente: Elaboración propia. 
 
 
Figura 21a. Trayectoria en iteración 32. Fuente: 
Elaboración propia. 
Figura 21b. Trayectoria en iteración 50 (última). Fuente: 
Elaboración propia.
 
 
Figura 23a. Trayectoria con 50 hormigas. Fuente: 
Elaboración propia. 
Figura 23b. Trayectoria con 50 hormigas. Fuente: 
Elaboración propia. 
22 
 
Para una tercera prueba, pero con una cantidad superior de hormigas como de iteraciones, 
100 y 100 respectivamente, los resultados arrojados son que haya menos trayectos cruzados 
entre sí pero los costos se aumentan un poco. Véase la figura 24a y la figura 24b. 
 
Entonces podemos decir que a mayor cantidad de hormigas se tengan predeterminadas en 
el algoritmo, menor va a ser la posibilidad de que una trayectoria se cruce con otra. Caso en 
que las iteraciones, las cuales mayor significa más recursos y por ende mayor tiempo de 
ejecución, con demasiadas iteraciones el tiempo de ejecución del algoritmo se volvería lento 
dependiendo de la computadora que sea utilizada. 
 
6 Análisis y Resultados 
En la tabla 1 se ubican los datos recogidos de las figuras 22 y 23b, las cuales presentan la 
distancia de recorrido para cierta iteración en la ejecución de ACO en dos distintas 
situaciones; la primera situación usando sólo 40 hormigas mientras la segunda se usan 50. 
Es evidente la diferencia en la distancia recorrida que realizan las hormigas en cada 
iteración. Para una mejor visualización de estos datos, la gráfica 1 representa dichas 
diferencias en donde vemos la mejora de la distancia. Esto conlleva a que la mejoría de la 
distancia, que es la razón es este proyecto, se logre con una pequeña variación en la 
cantidad de hormigas trabajando. 
 
 
Figura 24a. Trayectoria con 100 hormigas y 100 
iteraciones. Fuente: Elaboración propia. 
Figura 24b. Costos con 100 hormigas y 100 iteraciones. 
Fuente: Elaboración propia. 
 
 
23 
 
 
Por otro lado, como se pudo observar anteriormente en las pruebas, el algoritmo realiza la 
lectura de puntos, la identificación de posicionamiento de los mismos y el trazo de la 
trayectoria entre estos pero, la fidelidad de la lectura de puntos no es del 100% por factores 
externos al algoritmo, sean estos, la luz y/o distancia entre cámara y la PCB. En primeras 
pruebas, la iluminación, conformada por cuatro pequeños LEDs, era insuficiente y cada LED 
iluminaba una parte en específico pero esto ocasionaba que quedaran zonas oscuras, véase 
la figura 25, es decir, la iluminación no era uniforme sobre las tarjetas PCBs. Luego, se usó 
una lámpara LED de 3W que genera una iluminación más uniforme sobre las placas tal como 
se aprecia en la figura 26.. 
 
 
 
Tabla 1. Comparativa de distancia recorrida por 40 
hormigas VS 50 hormigas. Fuente: Elaboración propia. 
Gráfica 1. Comparativa de distancia recorrida por 40 
hormigas VS 50 hormigas. Fuente: Elaboración propia. 
24 
 
 
El rango de enfoque que tiene la cámara, dentro del espacio controlado, es muy limitado, por 
ende, para una PCB “grande”, se va a detallar un desenfoque en todos los bordes de la placa 
como se evidencia en la figura 27. Los puntos que allí se encuentren podrán ser o no 
identificados. 
 
Además, se evidencian dos casos al momento de la lectura de puntos. En el primer caso, la 
identificación de puntos se encuentra por debajo del 100%, esto es, leer menos puntos del 
valor real; En segundo caso, identificar puntos inexistentes, es decir, debido a los factores 
externos el algoritmo puede leer una mancha en la placa como un posible punto y de ahí en 
adelante trazar suruta tomando este punto como referencia. La figura 29 nos señala como 
algunos puntos no fueron identificados, por otro lado, la figura 29 señala punto identificados 
en zonas sin los mismos. 
 
 
Figura 27. Bordes no nítidos por poco enfoque debido a la distancia entre 
cámara y PCB. Fuente: Elaboración propia. 
Figura 25. Iluminación no uniforme. Fuente: Elaboración 
propia. 
Figura 26. Iluminación más uniforme. Fuente: Elaboración 
propia. 
 
 
25 
 
 
 
 
 
La resolución de este proyecto, como se aprecia, es en su mayoría un desarrollo de un 
código más que una maqueta o prototipo como tal. En nuestro primer objetivo se realiza la 
maqueta controlada en la cual se ubica nuestra capturadora de imagen, la cual, sus 
características permiten la facilidad de comunicación con nuestro software de MATLAB y 
desde este realizar el desarrollo del algoritmo, dando por cumplido este. Ya para el segundo 
objetivo, en el que se da el procesamiento de la imagen captada y así mismo la definición de 
orificios mediante este procesamiento, la imagen es modificada a una escala de grises de 
forma que se permita que las zonas claras tengan mayor apreciación a diferencia de las 
 
Figura 28. Puntos no identificados por el algoritmo. Fuente: Elaboración propia. 
 
Figura 29. Puntos identificados en lugares que no los tiene.. Fuente: Elaboración 
propia. 
26 
 
oscuras. Con esto hecho, el programa reconocerá los puntos blancos con mayor probabilidad 
y así podrá definirlos y almacenar su posición en una matriz que más adelante será llamada 
en la generación de las rutas cumpliendo así el segundo objetivo (en otro caso, el algoritmo 
también se puede modificar para que lea punto no blanco sino negros, y en este caso, la 
conversión a escala de grises ya no sería necesaria). En la ejecución del tercer objetivo, la 
inclusión de un algoritmo de ruleta para la definición de ruta es esencial, pues estos dan la 
pauta inicial para así poder tener algo que optimizar. La ruleta ayudará a las hormigas a tener 
una probabilidad de escoger una ruta (a parte del propio dado por el ACO) mientras que la 
ruta definirá la trayectoria que están haciendo las hormigas. Propiamente en este objetivo, el 
ACO se desarrolla teniendo en cuenta la cantidad de hormigas que se desean usar y la 
cantidad de recorridos que se desean que estas realicen. Se configura que cantidad de 
feromona se emitirá en cada recorrido y así mismo que tan rápido se evaporará. También, a 
cada hormiga se les asignan dos variables que controlan la probabilidad de escoger un 
camino por la experiencia entregada por la cantidad de feromona o por la intuición de 
explorar un nuevo camino. 
Finalmente, en comparativa del ACO con una ejecución del código G nos muestra que las 
hormigas tienen una decisión autónoma de escoger la ruta a seguir a diferencia de la 
simulación de CNC en la cual agentes externos al programa deciden que ruta seguir. Por 
ende, al ser el ACO un programa autónomo este puede ejecutar infinidad de rutas (hablemos 
de la cantidad de iteraciones) compararlas entre si y definir cuál es la ruta más óptima para 
seguir a diferencia del código G que solo tiene una ruta a seguir pues para rutas alternas se 
debería de reescribir y eso se traduce en gasto de tiempo de escritura y de pensar en que 
ruta sería bueno escribir. 
 
Conclusiones 
 
 
27 
 
Gracias a la aplicación de los ACO para la optimización de trayectorias, estas reducen 
considerablemente el recorrido hecho sobre las placas PCB, y, por ende, se reducen los 
tiempos de ejecución de la tarea. Comparando con las máquinas CNC, que trabajan 
mediante órdenes en códigos numéricos y que son insertados de forma manual, lo cual 
significa tiempo de trabajo, la optimización mediante ACO elimina el ingreso de datos 
manuales y ordenes específicas, disminuyendo el tiempo de trabajo y aumentando el que 
puede ser usado en más fabricación de PCB. Así mismo, basándonos en las pruebas 
realizadas, se comprueba que en la optimización los mejores resultados se obtienen con una 
mayor cantidad de hormigas, esto es, evitar que la trayectoria del taladro pase por el mismo 
punto varias veces, y no nos referimos al punto de perforación, sino a los puntos donde por 
desplazamiento del brazo se cruzan ocasionando reiteración y pérdida de tiempo en aquel 
cruce. También, debemos entender que el surgimiento de estos métodos de aplicación de las 
ACO está desarrollado para apuntar al mejoramiento continuo de las técnicas existentes y a 
la investigación de nuevas que permitan optimizar y mejorar los tiempos de cómputo. 
 
Referencias 
[1] K. Altinkemer, B. Kazaz, M. K¨oksalan, and H. Moskowitz, “Optimization of printed 
circuit board manufacturing: Integrated modeling and algorithms,” European Journal of 
Operational Research, vol. 124, no. 2, pp. 409–421, 2000. 
 
[2] Abbas, A. T., Aly, M. F.,Hamza K, Optimum drilling path planning for a rectangular 
matrix of holes using ant colony optimisation. International Journal of Production 
Research, doi:10.1080/00207543.2010.507608, 2010. 
 
[3] Duŝan Teodorović, Mauro Dell’ Orco. Bee Colony Optimization – A cooperative 
learning approach to complex transportation problems. Advanced OR and AI Methods 
in Transportation. 
 
[4] Xin-She Yang, Engineering Optimization. An Introduction with Metaheuristic 
Applications, Wiley, 2010. 
28 
 
 
[5] L. M. Gambardella M. Dorigo. Ant colonies for the traveling salesman problem. 
BioSystems, 43:73–81, 1997. 
 
[6] M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.