tag:blogger.com,1999:blog-22369096961158807872024-03-12T18:59:36.164-07:00Topicos Selectos de OptimizacionOsvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-2236909696115880787.post-66352667686603407382012-07-12T17:14:00.000-07:002012-07-12T20:09:48.080-07:00Graficas generadas por los archivos generados anteriormente: <br />
<br />
Búsqueda Local<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj7rJpnIEo91dNHM-n5wlLJRqoWjBdd275es5oa_1X7yRXFmYOgZzlTLhD5bgae5H2c_DoDD4wdSj1nAuC31j_J-ObJlFpCq-SgFdTAsVP2rRr_PUdy1NoU5ggvl7Hd_tEKT4vAPY5oLtQ/s1600/ar1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="281" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj7rJpnIEo91dNHM-n5wlLJRqoWjBdd275es5oa_1X7yRXFmYOgZzlTLhD5bgae5H2c_DoDD4wdSj1nAuC31j_J-ObJlFpCq-SgFdTAsVP2rRr_PUdy1NoU5ggvl7Hd_tEKT4vAPY5oLtQ/s400/ar1.png" width="400" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Búsqueda Tabú<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgFgBp_6AErSL1P8KYWGlnxd8kbm7m2cxD6-BhQcpjWw19INRrCnh7WVYswGetXo4ladN_DH6cIXOBptB74YKKBwy1RZviNWVrLA6jQ4CCFjHiGHG6YrJQZzOsTCXUxyr6H4hGe5zPh594/s1600/ar2.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="280" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgFgBp_6AErSL1P8KYWGlnxd8kbm7m2cxD6-BhQcpjWw19INRrCnh7WVYswGetXo4ladN_DH6cIXOBptB74YKKBwy1RZviNWVrLA6jQ4CCFjHiGHG6YrJQZzOsTCXUxyr6H4hGe5zPh594/s400/ar2.png" width="400" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Recocido Simulado<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbDOGLCrWcVBgn46C_9G2ZSAKYFkkINGp2LwIle7vtDQrVZjUbJYgj6xlC-dA-VsUDWFT_neqCKCG3i2S6D5jURmHC_2VQqovfrrIEztoQfHHqSC7THjp08rVdXr9ViX-TMmS-wsREdaE/s1600/ar3.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="281" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbDOGLCrWcVBgn46C_9G2ZSAKYFkkINGp2LwIle7vtDQrVZjUbJYgj6xlC-dA-VsUDWFT_neqCKCG3i2S6D5jURmHC_2VQqovfrrIEztoQfHHqSC7THjp08rVdXr9ViX-TMmS-wsREdaE/s400/ar3.png" width="400" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Genético<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1aRL4sJTHcVmt4Fsta-84CbCBSwE1oe1uUCnbv6eFbjZKhxOrhlXMHmm115o9ZaAFRw-CNs-FvWZwgLlnfXp5Rf-HFXaspUaqPBN54v1nx1XdSaW-JDb49_lBbx379qY31IC4_VFfblA/s1600/ar4.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="281" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1aRL4sJTHcVmt4Fsta-84CbCBSwE1oe1uUCnbv6eFbjZKhxOrhlXMHmm115o9ZaAFRw-CNs-FvWZwgLlnfXp5Rf-HFXaspUaqPBN54v1nx1XdSaW-JDb49_lBbx379qY31IC4_VFfblA/s400/ar4.png" width="400" /></a><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Se llego a la conclusión de que los 4 métodos tiene una complejidad asintótica de log(n) ya que se checo el código cada uno de los métodos y la siguientes gráfica muestra algunas complejidades asintóticas y vemos la que nosotros tenemos en nuestro código:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7CWz_8_m8jxWgJqJNr34o0V2h6X0bk2D2ogNhITJYmXy5oSD4yUNd94YsLVUrI5oTaS8HSEUFeesWQO1v6_V4KyJsk4TKT_tKCYnesq64tWVBrBmTcVWbW9H9eRwQ_IsFnmC1hsUFB_Y/s1600/al2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7CWz_8_m8jxWgJqJNr34o0V2h6X0bk2D2ogNhITJYmXy5oSD4yUNd94YsLVUrI5oTaS8HSEUFeesWQO1v6_V4KyJsk4TKT_tKCYnesq64tWVBrBmTcVWbW9H9eRwQ_IsFnmC1hsUFB_Y/s1600/al2.png" /></a></div>
<br />
<br />
Una explicación es que en el código contenían while, y vemos en la gráfica como aumenta lentamente al igual que en las nuestras.<br />
<br />
Programa para crear las graficas:<br />
<br />
<script src="https://gist.github.com/3102436.js"> </script>Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-40959011448433390302012-07-12T06:56:00.000-07:002012-07-12T07:27:41.352-07:00Visualización de evaluación de heurísticos
<br />
<br />
Para poder realizar la entrada de hoy nececitamos los archivos que se crearon ayer con el script corre.sh que nos creaba las instancias dependiendo de los datos que le diéramos, en nuestro caso algunos ejemplos son:<br />
<br />
<ul>
<li>instancia_20_1.dat_con_genetico.dat.stats</li>
<li>instancia_20_2.dat_con_local.dat.stats</li>
</ul>
<br />
Ahora vamos a graficar:<br />
<br />
<ul>
<li>Tiempo</li>
<li>Memoria </li>
<li>Objetivo</li>
<li>Objetivo/tiempo</li>
<li>Objetivo/Memoria</li>
<li>Objetivo/(Tiempo * Memoria)</li>
<li> </li>
</ul>
Las graficasreflejan el desempeño de cada método en lo mencionado anteriormente, recuerden que fueron:<br />
<ul>
<li>Búsqueda Local</li>
<li>Recocido simulado</li>
<li>Búsqueda Tabú</li>
<li>Algoritmo Genético</li>
<li>Hiperheuristico </li>
</ul>
<br />
Estas gráficas se realizaran para una cantidad de nodos de 20, 30, 50 y 60<br />
<br />
<br />
<br />
<script src="https://gist.github.com/3098231.js">
</script>
<br />
<br />
<br />
Cuando se ejecuta el script anterior genera nuevos archivosllamados:<br />
<ul>
<li>resultado_20</li>
<li>resultado_30</li>
<li>resultado_50</li>
<li>resultado_60</li>
</ul>
<br />
También necesitamos el script awk:<br />
<script src="https://gist.github.com/3098289.js">
</script>
<br />
<br />
<br />
Los archivos anteriores se utilizan para poder generar la grafica en gnuplot el código del archivo plot es:<br />
<script src="https://gist.github.com/3098269.js">
</script>
<br />
<br />
<br />
Imagen de la grafica<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDBMjfTWo8k5LnAQxv2WhKrTLkHQ8gxe9PQrMOqiseczGOkIMYBUlnnyaXnD5Xgx2ZJTecmzz1XfmTYTBwNtxKb4fqlCjMP44BWGaVJm2q5GbVSoiT_Ao5RFVJ1ejXUsAQHXVrBdCU8Bo/s1600/agraficas.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDBMjfTWo8k5LnAQxv2WhKrTLkHQ8gxe9PQrMOqiseczGOkIMYBUlnnyaXnD5Xgx2ZJTecmzz1XfmTYTBwNtxKb4fqlCjMP44BWGaVJm2q5GbVSoiT_Ao5RFVJ1ejXUsAQHXVrBdCU8Bo/s640/agraficas.png" width="640" /></a></div>
<br />
EL eje de las y significa lo siguientes:<br />
<br />
<ul>
<li>BL= Local</li>
<li>BT=Búsqueda Tabú</li>
<li>RS=Recocido Simulado</li>
<li>AG=Algoritmo Genético</li>
<li>HH=Hiperheuristico </li>
</ul>
Hablando de la cuestión en 20 nodos: <br />
<ul>
</ul>
En conclusión con los resultados podemos observar que en cuestión de Tiempo la búsqueda Tabú es mas efectiva, en cuestión de memoria Búsqueda Tabú.Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-81735081415639053942012-07-11T07:35:00.001-07:002012-07-11T07:38:44.339-07:00Análisis estadístico de desempeño<br />
<br />
En esta ocacion el codigo que utilizamos
<script src="https://gist.github.com/3090728.js">
</script>
Tambien tenemos el archivo bash:
<script src="https://gist.github.com/3090734.js">
</script>
El bash lo usamos para crear las instancias que queramos y crearnos los archivos con los resultados de cada uno de los métodos.
<br />
Resultados arrojados:<br />
<br />
Po Genetico: <br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSLg5rBMulvuBYNNdWjE2t6hcTKNpVe8kuD-nrsh3jDXPcPPvHGQTm3qk1DwaCrEdHcw9SarFUA7CEB7FvCgXTVAuQy0jyflHx3T2j321hkybC1hY04uF_2MsHlznXt-bBc8JCodkzzG8/s1600/at1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSLg5rBMulvuBYNNdWjE2t6hcTKNpVe8kuD-nrsh3jDXPcPPvHGQTm3qk1DwaCrEdHcw9SarFUA7CEB7FvCgXTVAuQy0jyflHx3T2j321hkybC1hY04uF_2MsHlznXt-bBc8JCodkzzG8/s400/at1.png" width="305" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Por hiperheuristica:</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGWKV3Ev5wbONCD2_93nueKYikfEmJX1g5W3KfAFeeruK7W0PETrzQsrScYR12i_WMwKgJ_YE8PVV06iE1L3dndTdJ2unNOFJfLHqAoCW5_H5n08VUtcx0-O_cpAel-vJI-6Mmn6QKsHU/s1600/at2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGWKV3Ev5wbONCD2_93nueKYikfEmJX1g5W3KfAFeeruK7W0PETrzQsrScYR12i_WMwKgJ_YE8PVV06iE1L3dndTdJ2unNOFJfLHqAoCW5_H5n08VUtcx0-O_cpAel-vJI-6Mmn6QKsHU/s400/at2.png" width="282" /></a><br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Por busqueda local</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcGvKyXImZiBa1V3RAAfxhrdBGNzNY2fNbpXTmOBPHWTMiNgxbHA5FTJXQnCPkM6WehNNvHQTks46BTW5XpugzTDkCJsE77A98FQE9lASbGlSU7FM9D52WsmSpkH2o5tNlHdDf8Tr8AF0/s1600/at3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcGvKyXImZiBa1V3RAAfxhrdBGNzNY2fNbpXTmOBPHWTMiNgxbHA5FTJXQnCPkM6WehNNvHQTks46BTW5XpugzTDkCJsE77A98FQE9lASbGlSU7FM9D52WsmSpkH2o5tNlHdDf8Tr8AF0/s400/at3.png" width="289" /></a><br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Por simulado recocido</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhKg3EMoaxW5gHDS-wMwL2NlKNWwqrfe0b31g4DWVu6hyphenhyphenDkZ1_fiory3y6g8gBU-rZuxNOusMS98qeSAvQU5geowsmAaq1HhGOR9nmHoiHM2X0oQ6jkkJ0jHVmHPgy_ckNc5SdudmRN5Y/s1600/at4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhKg3EMoaxW5gHDS-wMwL2NlKNWwqrfe0b31g4DWVu6hyphenhyphenDkZ1_fiory3y6g8gBU-rZuxNOusMS98qeSAvQU5geowsmAaq1HhGOR9nmHoiHM2X0oQ6jkkJ0jHVmHPgy_ckNc5SdudmRN5Y/s400/at4.png" width="313" /></a><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Por tabu</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiW3aWvDXZlom5dPtPNbh5cLLmHq21g4DzAeRIAsAP_XbzLcxq1wbqn2iQIZq7upKOlIGoM4kB3b7PKnq1FJhLQFf4eSqFUII2oX0Re_IhitQ7A6GJXjighosbrY2Uz_fxbjIQIh2mJTx8/s1600/at5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiW3aWvDXZlom5dPtPNbh5cLLmHq21g4DzAeRIAsAP_XbzLcxq1wbqn2iQIZq7upKOlIGoM4kB3b7PKnq1FJhLQFf4eSqFUII2oX0Re_IhitQ7A6GJXjighosbrY2Uz_fxbjIQIh2mJTx8/s400/at5.png" width="300" /></a>Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-1517407673334092632012-07-11T07:25:00.000-07:002012-07-11T07:25:11.993-07:00Análisis estadístico de desempeño<span style="font-size: large;">Análisis estadístico de desempeño </span><br />
<br />
<span style="font-size: large;"><span style="font-size: small;">Para poder medir el rendimiento de un programa necesitamos el tiempo que tarda el programa en ejecutarse, la memoria que ocupa así como también si es o no la respuesta arrojada es de buena calidad.</span></span><br />
<br />
<span style="font-size: large;"><span style="font-size: small;">Para esto el programa genera la matriz de adyacencia en un ".dat".</span></span><br />
<span style="font-size: large;"><span style="font-size: small;">Hicimos otro ".dat" con cada configuracion de cada metodo.</span></span><br />
<span style="font-size: large;"><span style="font-size: small;">Como resultado, el programa genera un ".dat" por cada metodo con los resultados (tiempo, memoria y calidad).</span></span><br />
<br />
<span style="font-size: large;"><span style="font-size: small;">Correrlo: </span></span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtmjdbvD7HzeIuUAOcuSYGynuECPWTBbyuJhRrNL9PK_Sgnh3Pdu814xHA7HIglVKZo2zxGXjDZC9XePTW9lXf2Nt4kYNQcEAyTerkAsX2f4mLLeJxBALEYEQeRPSJrUSZiHPZko0VN7NL/s1600/1111.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="158" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtmjdbvD7HzeIuUAOcuSYGynuECPWTBbyuJhRrNL9PK_Sgnh3Pdu814xHA7HIglVKZo2zxGXjDZC9XePTW9lXf2Nt4kYNQcEAyTerkAsX2f4mLLeJxBALEYEQeRPSJrUSZiHPZko0VN7NL/s400/1111.png" width="400" /></a></div><span style="font-size: large;"><span style="font-size: small;"><br />
Despues le pasamos el archivo creado + la configuracion al programa.</span></span><br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<span style="font-size: large;"><span style="font-size: small;">Estructura del archivo "config.dat"</span></span><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6SNW3x8MM52z3sYHb2lJwLr7FRUL8bhVe-pCeq6ycSxVwHAT3O6cCngvtdekOBH82Rage54u8f77coPA5zP8nwWWk3qPq5qN0zsyGwdOT6OH_6fFf2QOkj4fooY1lSQzI9MPy1WGBnVcR/s1600/22222.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6SNW3x8MM52z3sYHb2lJwLr7FRUL8bhVe-pCeq6ycSxVwHAT3O6cCngvtdekOBH82Rage54u8f77coPA5zP8nwWWk3qPq5qN0zsyGwdOT6OH_6fFf2QOkj4fooY1lSQzI9MPy1WGBnVcR/s1600/22222.png" /></a></div><br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<span style="font-size: large;"><span style="font-size: small;">Generar los tiempos, calidad y memoria para este ejemplo.</span></span><br />
<br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<br />
<br />
<br />
<br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<span style="font-size: large;"><span style="font-size: small;"><br />
</span></span><br />
<br />
<br />
<br />
<span style="font-size: large;"><span style="font-size: small;"> </span></span>Osvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.com0tag:blogger.com,1999:blog-2236909696115880787.post-49746091457166795362012-07-10T04:17:00.000-07:002012-07-10T04:17:27.663-07:00Hiperheuristica:<br />
<br />
En esta oacion lo que hacemos es que el programa escoja uno de los cuatro métodos que tenemos que son:<br />
<br />
<ul>
<li>local</li>
<li>tabu</li>
<li>recocido</li>
<li>genetico</li>
</ul>
Cuando comienza un reinicio se comienza a realizar un método en cada reinicio se realiza uno diferente o el mismo dependiendo de lo que nos arroje el programa.<br />
<br />
El código que utilizamos para realizar esto fue el siguiente:<br />
<br />
<script src="https://gist.github.com/3082705.js">
</script>
Tambien se cambio la parte de la funcion grafica además de que creo una nueva funcion llamada ruleta:<br />
<br />
<br />
<script src="https://gist.github.com/3082714.js">
</script>
Lo que hace es regresarnos el método seleccionado.Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com2tag:blogger.com,1999:blog-2236909696115880787.post-11380926928741560832012-07-09T04:38:00.000-07:002012-07-09T04:54:44.294-07:00Genetico:<br />
<br />
Codigo<br />
<br />
El codigo que utilizamos para el geetico fue el siguiente:<br />
<br />
<br />
<script src="https://gist.github.com/3075994.js">
</script>
Al mismo tiempo tambien se modificaron algunas funciones para poder realizar esto mas facilmente.<br />
<br />
Lo que se realiza en esta parte de genetico es que primero se genera una poblaciones de posibles soluciones factibles, esta poblacion realiza un cruzamiento y mutaciones aleatorias despues se obtienen los mejores individuos y los demas se sacrifican.<br />
<br />
Graficas que fueron arrojadas<br />
<br />
Datos utilizados<br />
<br />
Nodos: 20<br />
Densidad: .6<br />
Cantidad de reinicios: 4<br />
Maxima cantidad de intentos fallidos: 10<br />
<br /><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr0XPWhT7tTrXV68odqKmd3wbi5PjWNt6aYqIho5uZsAoZ3blWRB_65Um8_9j-hRt7T9qiSbav5hbafEUMa8L6H-vYC9yK-d50jsOhPC4PWleyv6HtBCK0x_ZVoFW-pLBsqt3LlIWok4s/s1600/agenetico1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr0XPWhT7tTrXV68odqKmd3wbi5PjWNt6aYqIho5uZsAoZ3blWRB_65Um8_9j-hRt7T9qiSbav5hbafEUMa8L6H-vYC9yK-d50jsOhPC4PWleyv6HtBCK0x_ZVoFW-pLBsqt3LlIWok4s/s640/agenetico1.png" width="640" /></a></div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiypJp8zU3oJ8cb65n20HdrrfUWmvVBPannc4ZO71YHXq8xSzStMJWbzhfExHeAKHaGiGW_EN8wv8zbVsr_aKc7H8kFFUkOUZ_12NtrTaDTK0D5EI49adqkrIXFSOe8SPKE5ANpxKYdbS0/s1600/a_gen1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="220" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiypJp8zU3oJ8cb65n20HdrrfUWmvVBPannc4ZO71YHXq8xSzStMJWbzhfExHeAKHaGiGW_EN8wv8zbVsr_aKc7H8kFFUkOUZ_12NtrTaDTK0D5EI49adqkrIXFSOe8SPKE5ANpxKYdbS0/s640/a_gen1.png" width="640" /></a></div>
<br />
<br />
<br />Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com0tag:blogger.com,1999:blog-2236909696115880787.post-52176375929622418652012-07-04T14:50:00.000-07:002012-07-04T18:00:39.989-07:00Metaheurística de recocido simulado
<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
AL utilizar la metaheurística de recocido simulado se busca encontrar una buena aproximación al valor óptimo<br />
<br />
Para poder realizar esto se modifico el codigo de la función busqueda() y de main
<script src="https://gist.github.com/3049774.js">
</script>
Como se muestra se crearon nuevas variables las cuales fueron tempraturaInicial y enfriamiento.
<script src="https://gist.github.com/3049785.js">
</script><br />
<br />
A continuación se presentan las graficas donde se le da un tamaño a la lista Tabu (Utilizamos la lista tabu y la metaheuristica recocido simulado):<br />
<br />
Datos con los que se genero:<br />
<br />
Número de nodos = 15<br />
Número del clique inicial =4<br />
Densidad = .5<br />
Reinicios = 100<br />
Oportunidades maximas:20<br />
Tamaño de la lista Tabu: 10<br />
Temperatura inicial: 1000<br />
<br />
El enfriamiento va a depender por eso creamos 5 graficas:<br />
<br />
Grafica 1 enfriamiento =.45<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs5rMiFc_lPlG4mEdWEpCLhoqOpaEmU4foY_Cs_SEbjqge1OnfSdIbFTIfJMmu5f59AU0hCkRuMR5884I5qnmLons-XY6rEeBN2DQPRlV3YPO-x3vDE5wRauNWo97dWG-r6hdkKoYFrmcj/s1600/a1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="230" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs5rMiFc_lPlG4mEdWEpCLhoqOpaEmU4foY_Cs_SEbjqge1OnfSdIbFTIfJMmu5f59AU0hCkRuMR5884I5qnmLons-XY6rEeBN2DQPRlV3YPO-x3vDE5wRauNWo97dWG-r6hdkKoYFrmcj/s640/a1.png" width="640" /></a></div>
<br />
<br />
Grafica 2 enfriamiento = .65<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHmaUJPrkclA0e4_LtgZYjIAcEjZsmAB2XZteehf3LzAQRlkC2fISY1qHKSSJ46MtKPjr-nkJpwVstDt2-1QAAVh9PcUYgFnLI2xVNRKaw4Fcd6gLPZfqxoX_o729i11P1KUz-tpRhhv2L/s1600/as2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="225" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHmaUJPrkclA0e4_LtgZYjIAcEjZsmAB2XZteehf3LzAQRlkC2fISY1qHKSSJ46MtKPjr-nkJpwVstDt2-1QAAVh9PcUYgFnLI2xVNRKaw4Fcd6gLPZfqxoX_o729i11P1KUz-tpRhhv2L/s640/as2.png" width="640" /></a></div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
Grafica 3 enfriamiento = .70<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaqOSyJgKyMKUxeEdV1-wBbEs5uQNqgJaEfFnaZItVGN4t2u3MoV22watPbcP-bzDuvjutQcexs6F8jJ-uFsnDI2QOxaXmbjOiQ2mK6tMSJONAlPH0iguWmjmiB7_IEnE4ukn9YesE4vms/s1600/as3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaqOSyJgKyMKUxeEdV1-wBbEs5uQNqgJaEfFnaZItVGN4t2u3MoV22watPbcP-bzDuvjutQcexs6F8jJ-uFsnDI2QOxaXmbjOiQ2mK6tMSJONAlPH0iguWmjmiB7_IEnE4ukn9YesE4vms/s640/as3.png" width="640" /></a></div>
<br />
<br />
Grafica 4 enfriamiento = .85<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg49GJHHDISI9EhoyircvYHj9AhvRcCxypzFcCG8FwM8Vc602nIjj-_h6tnEgW-hXmNgcVh-kVEHZX-AnD-VBs-TJbWFVgxzOqzk3CWHgEtOrnWcKuq58okPHKe-52I0YTLokFZWcgTVIwV/s1600/a4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="228" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg49GJHHDISI9EhoyircvYHj9AhvRcCxypzFcCG8FwM8Vc602nIjj-_h6tnEgW-hXmNgcVh-kVEHZX-AnD-VBs-TJbWFVgxzOqzk3CWHgEtOrnWcKuq58okPHKe-52I0YTLokFZWcgTVIwV/s640/a4.png" width="640" /></a></div>
<br />
<br />
GRafica 5 enfriamiento = .95<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaDQnWLveTlWdzLH5PtftmGLmYl8CcaNQkXiaES0Dx0xCspf1A5YtPbWo5r4s8X27P3E9V87JHQW46fAnuEgI7a9UZLah5ofHoQX_avldrN_4fsy0o81qUcjgdBvv8LyztiXFLfOga6G2D/s1600/a5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="228" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaDQnWLveTlWdzLH5PtftmGLmYl8CcaNQkXiaES0Dx0xCspf1A5YtPbWo5r4s8X27P3E9V87JHQW46fAnuEgI7a9UZLah5ofHoQX_avldrN_4fsy0o81qUcjgdBvv8LyztiXFLfOga6G2D/s640/a5.png" width="640" /></a></div>
<br />
Ahora realizaremos 5 graficas mas pero dandole un tamaño de 0 a nuestra busqueda Tabu<br />
<br />
Grafica 1 enfriamiento =.45<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_skR9-0EQR7SjSx5J_okdNSjacuyuVSEERkN2x32tQ4bc8g6VKVIt8I14UBcxUSWLSkeCUAHQkb8ntB5m4srlMi3BP-4FzafMNRPi9EsBvDWBaZC_MyZVshYKxlTzReO_ycXKoniY0umM/s1600/b1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="226" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_skR9-0EQR7SjSx5J_okdNSjacuyuVSEERkN2x32tQ4bc8g6VKVIt8I14UBcxUSWLSkeCUAHQkb8ntB5m4srlMi3BP-4FzafMNRPi9EsBvDWBaZC_MyZVshYKxlTzReO_ycXKoniY0umM/s640/b1.png" width="640" /></a></div>
<br />
<br />
Grafica 2 enfriamiento = .65<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmj7oH4vUly0zMdQwPF7nrqZHrx5iGKO46xyzqlhtS4wsGJsrSKqVVumeMvqFxDAMMwsXg1hid5J75yMEO3lGfSCFy5uCdz4vtA_abkUb-_mNhjm1IWbHxcM8ev5dnd6lXfsoIJbv0yOju/s1600/b2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmj7oH4vUly0zMdQwPF7nrqZHrx5iGKO46xyzqlhtS4wsGJsrSKqVVumeMvqFxDAMMwsXg1hid5J75yMEO3lGfSCFy5uCdz4vtA_abkUb-_mNhjm1IWbHxcM8ev5dnd6lXfsoIJbv0yOju/s640/b2.png" width="640" /></a></div>
<br />
<br />
Grafica 3 enfriamiento = .70<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihhe5PgMIqiXS8wmE-f19d7wcKb7ETmDrOZC2qwF9D8JBPPNyzEWg7e7O805js7ksFEDbBzG2bP_KyMZAngH652dlyabp1RkhInyuACysFbPcOC8q-7cexzYuZwC9Q0IMzEUkRZqTmHw6B/s1600/b3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihhe5PgMIqiXS8wmE-f19d7wcKb7ETmDrOZC2qwF9D8JBPPNyzEWg7e7O805js7ksFEDbBzG2bP_KyMZAngH652dlyabp1RkhInyuACysFbPcOC8q-7cexzYuZwC9Q0IMzEUkRZqTmHw6B/s640/b3.png" width="640" /></a></div>
<br />
<br />
Grafica 4 enfriamiento = .85<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht_YjaZldnux6dhs1RRGCsidNcNrKqblG0ihDfvHjZNpY2NXll_JW13st26YJ01N81e2LCBNllAx0nJ-6AbSZuJbtzG9QzXeuJhVcDvTezv7lAkkEW_mF3HmHKAvMZX8NnmLVO9uOpD6zK/s1600/b4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="226" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht_YjaZldnux6dhs1RRGCsidNcNrKqblG0ihDfvHjZNpY2NXll_JW13st26YJ01N81e2LCBNllAx0nJ-6AbSZuJbtzG9QzXeuJhVcDvTezv7lAkkEW_mF3HmHKAvMZX8NnmLVO9uOpD6zK/s640/b4.png" width="640" /></a></div>
<br />
<br />
Grafica 5 enfriamiento = .95<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgeowiq8YrZtIwEjO450f0u5v1aXglA2oZC_Ifjjewz2vT8yC4aGwtg_jezs5_tktetKPNe4UUBOguOXypTvOv_xSgPuUJDSsJtsYkiGfZrOGZ2PYHJQ8txqvYDsuQMwM7p-iXVI0YkQPcf/s1600/b5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgeowiq8YrZtIwEjO450f0u5v1aXglA2oZC_Ifjjewz2vT8yC4aGwtg_jezs5_tktetKPNe4UUBOguOXypTvOv_xSgPuUJDSsJtsYkiGfZrOGZ2PYHJQ8txqvYDsuQMwM7p-iXVI0YkQPcf/s640/b5.png" width="640" /></a></div>Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-10506755687994843702012-07-04T03:08:00.001-07:002012-07-04T04:39:47.089-07:00Busqueda Tabu.
Para poder optimizar nuestra solución inicial se realizo una busqueda Tabu la cual consiste en realizar una lista en donde guardaremos la solución pero que esta no se repita:<br />
<br />
Código de la busqueda Tabu:<br />
<br />
<script src="https://gist.github.com/3046574.js">
</script>
<br />
<br />
Otras partes que se modificaron:<br />
<script src="https://gist.github.com/3046583.js">
</script>
<br />
<br />
Graficas arrojadas con tamaño distinto de la lista Tabu:<br />
<br />
Lista Tabu: 100<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-zxA-I8IWgsdqxiQ0_BVLw5uXcSGPtCI6zqLZD6v6l41boScCcWJWI2J7H_MrXT232vqELHrVsW4T9k5w6T8wSAcKg9UNKF3HeHrHfkwWqPsnUQrbS4ahbTH7oc4UbN2g-4-x51WeCWs/s1600/tab1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-zxA-I8IWgsdqxiQ0_BVLw5uXcSGPtCI6zqLZD6v6l41boScCcWJWI2J7H_MrXT232vqELHrVsW4T9k5w6T8wSAcKg9UNKF3HeHrHfkwWqPsnUQrbS4ahbTH7oc4UbN2g-4-x51WeCWs/s640/tab1.png" width="640" /></a></div>
<br />
Lista Tabu: 30 <br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwiwC9-wBZOq1NBE2oe-rn7Ao29hRiGAsZR3M4M2bSAut1nUadql34eLfnHmaXQwHk0WabZQaHZ8t07-1eZaOZJ5ZFreBPwE84Orhw4vnJN1K1r5Hv1mUwcQjt5Brk693pbn-PON0zvPc/s1600/tab2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwiwC9-wBZOq1NBE2oe-rn7Ao29hRiGAsZR3M4M2bSAut1nUadql34eLfnHmaXQwHk0WabZQaHZ8t07-1eZaOZJ5ZFreBPwE84Orhw4vnJN1K1r5Hv1mUwcQjt5Brk693pbn-PON0zvPc/s640/tab2.png" width="640" /></a></div>
<br />
Lista Tabu:300<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEgCFznJEezgzDordi4NJzFCGAih3TnFgqNi9aZNYNyMlXUw3RFp8K8NrzUTeAjtJeAiOMo8rJZNj9EZbCOrnHHTdsU-LadpTAZmbTtvp8JjUCTcvaj_KLwpw3zc-sfMdPFRga0r_TMEQ/s1600/ag3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEgCFznJEezgzDordi4NJzFCGAih3TnFgqNi9aZNYNyMlXUw3RFp8K8NrzUTeAjtJeAiOMo8rJZNj9EZbCOrnHHTdsU-LadpTAZmbTtvp8JjUCTcvaj_KLwpw3zc-sfMdPFRga0r_TMEQ/s640/ag3.png" width="640" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>Blanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-30972533997514709122012-07-03T03:55:00.001-07:002012-07-03T03:55:24.188-07:00busqueda local<div style="color: blue;">
<span style="font-size: x-large;">Busqueda Local</span></div>
<ul style="color: #38761d;">
<li>A veces el camino para llegar a la solución no nos importa, buscamos en el espacio de soluciones</li>
<li>Queremos la mejor de entre las soluciones posibles alcanzable en un tiempo razonable (el óptimo es imposible)</li>
<li>Tenemos una función que nos evalúa la calidad de la solución, pero que no esta ligada a ningún coste necesariamente</li>
<li>La búsqueda se realiza desde una solución inicial que intentamos mejorar modificándola (operadores)</li>
</ul>
<span style="font-size: large;">Busqueda Local aplicado al problema del clique</span><br />
<br />
<div style="color: black;">
<span style="font-family: inherit; font-size: small;"><span id="internal-source-marker_0.5442807512195383" style="background-color: transparent; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Basándonos de la "solución inicial" el programa estará interando </span><span style="background-color: transparent; font-style: italic; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">n </span><span style="background-color: transparent; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">veces,
comparando nodo por nodo, decidiendo y reasignando el nuevo valor de
"solución inicial" en caso de que la solución encontrada fuera mayor.</span></span></div>
<div style="color: black;">
<br /></div>
<div style="color: black;">
Como lo unico que importa es encontrar la solución, este algoritmo es lento.</div>
<div style="color: black;">
<br /></div>
<div style="color: red;">
Codigo:</div>
<div style="color: black;">
Funcion principal: Escarga de buscar un posibles cliques y comparlos con los anteriores.</div>
<div style="color: black;">
<br /></div>
<div style="color: black;">
<script src="http://pastebin.com/embed_js.php?i=eZqd6enh">
</script>
</div>
<div style="color: black;">
<br /></div>
<div style="color: black;">
Esta funcion se encarga de comparar un "posible clique" al "mayor clique". En caso de que este sea mayor devuelve un TRUE y el nuevo tamaño del clique.</div>
<div style="color: black;">
<br /></div>
<div style="color: black;">
<br />
<script src="http://pastebin.com/embed_js.php?i=UXexhzYC">
<br>
</script></div>
<div style="color: black;">
<br /></div>
<div style="color: black;">
Grafica:</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSKleN97cDVbnqt0b93ZkOEu9ujZhP5OrEQ48_utvf60bJKWAnAd2Pr7fBK_USVDMajB3zvRC2aokedpUBrP2tobma4aE-tbxNDd1BtRAbwJy1FKwVgyf2wRRvVfxxRbQfH0KDQvnsD92e/s1600/22222.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="111" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSKleN97cDVbnqt0b93ZkOEu9ujZhP5OrEQ48_utvf60bJKWAnAd2Pr7fBK_USVDMajB3zvRC2aokedpUBrP2tobma4aE-tbxNDd1BtRAbwJy1FKwVgyf2wRRvVfxxRbQfH0KDQvnsD92e/s320/22222.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiHMzwVrzs7ybR_zh33BuVb0cTtqJlhk8vXlV3-CWAgkeTFY5NDJCXLfQNAsxkHjWbvrh7UXuqAnpUIjtgGJ3xkJ6HjPXxqtTtDJ2IV7HMS6vkISBambX5ybdn0SCTe_fCIaNDEKRjECyus/s1600/grafica.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /></a></div>
<br />
<div style="color: black;">
Para generar esta grafica se usaron:</div>
<ul>
<li style="color: black;">nodos = 20</li>
<li style="color: black;">clique(inicial) = 7</li>
<li style="color: black;">Densidad = 0.5 </li>
<li style="color: black;">intentos 10</li>
<li><span style="color: black;">maxIntentos = 10</span></li>
</ul>
<br />Osvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-19865383882136108162012-06-29T09:59:00.000-07:002012-06-29T09:59:28.748-07:00soluciones inicialesPara nuestro problema tenemos que sacar la <u>funcion objetiva maxima</u>, porque tenemos que maximizar el tamaño del clique. <br />
<br />
Seleccionamos un nodo al azar, este es el nodo desde donde se comenzara a buscar el clique.<br />
<br />
Despues seleccionamos otro nodo y se busca el maximo clique que se crea asi sicesivamente se selecciona el maximo.<br />
<br />
La forma de hacerlo es que cada uno de los vertices estes conecatados con los demas vertices. <br />
<br />
<br />
<br />
Factibilidad:<br />
<br />
Tenemos que checar que si el tamaño del clique q nos arroja cumple con todas las restricciones que en este caso solo tenemos una que es que todos sus nodos esten conectados entre si.Osvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-28499123821196031382012-06-28T09:31:00.000-07:002012-06-28T09:31:56.285-07:00cotas<div style="color: blue;">
<span style="font-size: large;">Cotas Inferior y Superior</span></div>
<br />
<br />
¿Que son las cotas?<br />
Son rangos en los cuales debe de estar tu solución. Tus salidas NUNCA pueden estar por debajo o por ensima de estos rangos. <br />
<br />
Para sacar la <u style="color: red;"><b>cota inferior</b></u>, solamente pensamos en cual podia ser el minimo clique que se puede formar dentro de un grafo, asi que definicion es siempre un par.<br />
<br />
<br /><u style="color: red;"><b>Cota Superior</b></u><br />Lo que hicimos fue sumarle +1 al mayor grado que hay en el grafo. Porque no puede haber/existir otro clique en ese mismo grafo que pueda sobrepasar el grado (g+1).<br />
<br />
Código: <br />
<br />
<script src="https://gist.github.com/3012075.js">
</script> <br />
<br />
y la salida es:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlxHoT9fWAMDvHElEXkdLjgHLUXxh9h8hj0j1xI1i6H2PDRh8aeaUcIhJ57ohzJKplSbMH35-EzF5DecxgxwDSqB3P0razgOX9O2OWrPXa2kFjpCRwxzJeRJauREvFI777n7aHbxCgJoXv/s1600/1222" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="343" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhlxHoT9fWAMDvHElEXkdLjgHLUXxh9h8hj0j1xI1i6H2PDRh8aeaUcIhJ57ohzJKplSbMH35-EzF5DecxgxwDSqB3P0razgOX9O2OWrPXa2kFjpCRwxzJeRJauREvFI777n7aHbxCgJoXv/s400/1222" width="400" /></a></div>
<br />Osvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-32774597517655178142012-06-27T08:04:00.003-07:002012-06-27T09:37:58.806-07:00<div style="color: #0b5394; font-family: Georgia,"Times New Roman",serif;">
<span style="font-size: small;"><b>Sesión 2: Obtención y generación de instancias reales y
artificiales</b></span></div>
<div style="color: #0b5394;">
<br />
<br /></div>
Problema: Clique Maxima<br />
Lo que realiza el programa es que le damos valores a lo que es el clique inicial que queremos que se haga en el grafo, el tamaño de grafo y la densidad de las aristas:
<br />
Como correr el programa:<br />
<script src="https://gist.github.com/3005219.js">
</script>
<br />
Significdo de los numeros:<br />
5= Cantidad de nodos<br />
3= Clique inicial<br />
.5= Densidad de arista<br />
<br />
<br />
<br />
Código:
<script src="https://gist.github.com/3005185.js">
</script><br />
Después de correr el programa genera un archivo de salida .dat<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgiQXV4hOVubiOfqiYJQy_lt9vrPWNhK-y4fpccWYhQlMtxxjjUNHKWusLf-4gAjZv-hXHgk0s_xijqohTBqwidjhqxoEvLN9Ed7VPHWCraT8hWU0bYJ04lN5n4yFdJInFIoy0bi-e8SCU/s1600/1222.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgiQXV4hOVubiOfqiYJQy_lt9vrPWNhK-y4fpccWYhQlMtxxjjUNHKWusLf-4gAjZv-hXHgk0s_xijqohTBqwidjhqxoEvLN9Ed7VPHWCraT8hWU0bYJ04lN5n4yFdJInFIoy0bi-e8SCU/s1600/1222.png" /></a></div>
Benchmark:
<a href="http://cs.hbg.psu.edu/txn131/clique.html">Link1</a>
Como mejora realizaremos el grafo de forma graficaBlanca Rodríguezhttp://www.blogger.com/profile/14593237658990450210noreply@blogger.com1tag:blogger.com,1999:blog-2236909696115880787.post-2358483908019883032012-06-26T07:33:00.000-07:002012-06-26T08:12:03.666-07:00Introduccion<div style="color: blue;">
<span style="font-size: large;">Equipo:</span></div>
<br />
<div style="color: #666666;">
Osvaldo Javier Hinojosa Rdz - 1452344 {<span style="color: red;">Calificación: 80</span>}</div>
<div style="color: #666666;">
Blanca Alicia Rodriguez Rivas - 1458143 {<span style="color: red;">Calificación: 80</span>}</div>
<div style="color: #666666;">
Rafael Lopez Gutierrez - 1451428 {<span style="color: red;">Calificación: 80</span>}</div>
<br />
<div style="color: blue;">
<span style="font-size: large;">Lenguaje:</span></div>
<br />
PYTHON<br />
<div style="color: blue;">
<span style="font-size: large;">Definición del problema escogido:</span></div>
<br />
<div style="color: red;">
Clique Maximo</div>
<br />
<div style="color: #444444;">
Dado un grafo no dirigido G = V,E, donde V es un conjunto de vértices y E es el conjunto de bordes, se dice que dos vértices son adyacentes cuando están conectados por un borde. Se dice que el grafo es completo cuando dos vertices cualiesquiera son adyacentes y, cuando esto sucede, tambien se dice que el grafo es un clique. Un problema tipico es la obtencion del subconjunto maximo de vertices de V tal que sus elementos forman un clique. En este caso hablamos del "problema del maximo clique" (MCP). </div>
<div style="color: #444444;">
<br /></div>
<div style="color: #444444;">
La figura 5.6 ilustra el concepto de clique con un grafo de ejemplo formado por 4 elemtentos. el estudio de los cliques tiene importantes alicaiones practicas en campos como la vision por computador o el procesamiento de señales. En particular resulta gran interes en problemas de optmizacion combinacional, en aplicaciones como el analisis de mercados.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjTUx5m3WDg743eB7xIRi137Cq5zfysD_mpcIlkT5P_IAU0rXz61k0ZEW_W_ktJr67HKObp9SK_npihKTo3JVNDu2i5U7S97GVmOxYZxWSWAYSINWZzjrrtw9vtBSFi1xiLYsf2MpwC04U/s1600/clique.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjTUx5m3WDg743eB7xIRi137Cq5zfysD_mpcIlkT5P_IAU0rXz61k0ZEW_W_ktJr67HKObp9SK_npihKTo3JVNDu2i5U7S97GVmOxYZxWSWAYSINWZzjrrtw9vtBSFi1xiLYsf2MpwC04U/s1600/clique.png" /></a></div>
<br />
<br />
<div style="color: blue;">
<span style="font-size: large;">Complejidad:</span></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrzKk0U3V2u8D5xKvhDwJ6-n-o1yNS860R2C1BnZFkdAHqGJM_0LPDwsIBSZJ2BhBqRO9iViVGUbpMzZ_zakg1ELZXyADx_7g4o0LoS85eb6AvmmZqJRp-B0T9UcdbNCE52daLk7OIevAS/s1600/11111.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrzKk0U3V2u8D5xKvhDwJ6-n-o1yNS860R2C1BnZFkdAHqGJM_0LPDwsIBSZJ2BhBqRO9iViVGUbpMzZ_zakg1ELZXyADx_7g4o0LoS85eb6AvmmZqJRp-B0T9UcdbNCE52daLk7OIevAS/s1600/11111.png" /> </a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN-wpF2SWcEisZfMK-bXd3ZiBnJmg0HE39Z311Z4iYZOnbi3cQF-e-PAzT1chdojSBZ2QnrLQSBc9gubZ0rn4vVzSv_yjbooG9YwIGE0gghVjF3Jn6zsRo2-K_CP0aai1yoPKBRqrF6_4i/s1600/22222.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhN-wpF2SWcEisZfMK-bXd3ZiBnJmg0HE39Z311Z4iYZOnbi3cQF-e-PAzT1chdojSBZ2QnrLQSBc9gubZ0rn4vVzSv_yjbooG9YwIGE0gghVjF3Jn6zsRo2-K_CP0aai1yoPKBRqrF6_4i/s1600/22222.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="color: blue;">
<span style="font-size: large;">Problemas de decisión:</span></div>
<div style="color: #444444;">
<span style="background-color: white; display: inline ! important; float: none; font-family: sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 19px; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;"><span class="Apple-converted-space"></span><span style="font-family: inherit; font-size: small;">¿existe una clique de tamaño k en el grafo?</span></span></div>
<div style="color: blue;">
<span style="font-size: large;"><br /></span></div>
<div style="color: blue;">
<span style="font-size: large;">Tamaños de instancia:</span></div>
<div style="color: blue;">
<span style="font-size: large;"><span style="color: #444444; font-size: small;">aun investigando...</span><span style="color: #444444;"> </span></span></div>
<br />
<br />
<br />
<span style="color: blue; font-size: large;">Bibliografia:</span><br />
<br />
Problema de optimizacion:<br />
<ul>
<li><a href="http://www.scribd.com/doc/63957577/37/OTROS-PROBLEMAS-NP-COMPLETOS-147">http://www.scribd.com/doc/63957577/37/OTROS-PROBLEMAS-NP-COMPLETOS-147 </a></li>
<li><a href="http://www.scribd.com/doc/56237525/69/El-problema-del-maximo-clique">http://www.scribd.com/doc/56237525/69/El-problema-del-maximo-clique </a></li>
<li><a href="http://es.wikipedia.org/wiki/Problema_de_la_clique">http://es.wikipedia.org/wiki/Problema_de_la_clique</a></li>
</ul>
<br />
<br />Osvaldo Hinojosahttp://www.blogger.com/profile/05654564468175441216noreply@blogger.com1