Python 和 C++ 中最近字符串问题的蚁群优化异常行为
Unusual behaviour of Ant Colony Optimization for Closest String Problem in Python and C++
这可能是一个很长的问题，我提前道歉。
我正在做一个项目，目标是研究最近字符串问题的不同解决方案。
Let s_1, ... s_n be strings of length m. Find a string s of length m such that it minimizes max{d(s, s_i) | i = 1, ..., n}, where d is the hamming distance.
已尝试的一种解决方案是使用蚁群优化，如 here 所述。
论文本身并没有涉及实现细节，所以我已经尽力提高效率了。然而，效率并不是唯一的异常行为。
我不确定这样做是否常见，但我会通过 pastebin 展示我的代码，因为我相信如果我将它直接放在这里，它会淹没线程。如果这证明是一个问题，我不介意编辑线程直接把它放在这里。 正如我之前试验过的所有算法一样，我最初在 python 中编写了这个算法。这是代码：
def solve_(self, problem: CSProblem) -> CSSolution:
m, n, alphabet, strings = problem.m, problem.n, problem.alphabet, problem.strings
A = len(alphabet)
rho = self.config['RHO']
colony_size = self.config['COLONY_SIZE']
global_best_ant = None
global_best_metric = m
ants = np.full((colony_size, m), '')
world_trails = np.full((m, A), 1 / A)
for iteration in range(self.config['MAX_ITERS']):
local_best_ant = None
local_best_metric = m
for ant_idx in range(colony_size):
for next_character_index in range(m):
ants[ant_idx][next_character_index] = random.choices(alphabet, weights=world_trails[next_character_index], k=1)[0]
ant_metric = utils.problem_metric(ants[ant_idx], strings)
if ant_metric < local_best_metric:
local_best_metric = ant_metric
local_best_ant = ants[ant_idx]
# First we perform pheromone evaporation
for i in range(m):
for j in range(A):
world_trails[i][j] = world_trails[i][j] * (1 - rho)
# Now, using the elitist strategy, only the best ant is allowed to update his pheromone trails
best_ant_ys = (alphabet.index(a) for a in local_best_ant)
best_ant_xs = range(m)
for x, y in zip(best_ant_xs, best_ant_ys):
world_trails[x][y] = world_trails[x][y] + (1 - local_best_metric / m)
if local_best_metric < global_best_metric:
global_best_metric = local_best_metric
global_best_ant = local_best_ant
return CSSolution(''.join(global_best_ant), global_best_metric)
utils.problem_metric 函数如下所示：
def hamming_distance(s1, s2):
return sum(c1 != c2 for c1, c2 in zip(s1, s2))
def problem_metric(string, references):
return max(hamming_distance(string, r) for r in references)
我发现您可以向 ACO 添加更多的调整和其他参数，但我暂时保持简单。我使用的配置是 250 次迭代，蚁群大小为 od 10 只蚂蚁，rho=0.1。我正在测试它的问题来自这里： http://tcs.informatik.uos.de/research/csp_cssp ，那个叫做 2-10-250-1-0.csp （第一个） .字母表只有'0'和'1'组成，字符串长度为250，一共有10个字符串。
对于我提到的ACO配置，这个问题，使用python求解器，平均在5秒内解决，平均目标函数值为108.55（模拟20次）。正确的目标函数值是 96。具有讽刺意味的是，与我第一次尝试实施此解决方案时相比，5 秒的平均值已经很好了。然而，它仍然出奇地慢。
在进行各种优化后，我决定尝试在 C++ 中实现完全相同的解决方案，看看 运行 时间之间是否会有显着差异。这是 C++ 解决方案：
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <random>
#include <chrono>
#include <map>
class CSPProblem{
public:
int m;
int n;
std::vector<char> alphabet;
std::vector<std::string> strings;
CSPProblem(int m, int n, std::vector<char> alphabet, std::vector<std::string> strings)
: m(m), n(n), alphabet(alphabet), strings(strings)
{
}
static CSPProblem from_csp(std::string filepath){
std::ifstream file(filepath);
std::string line;
std::vector<std::string> input_lines;
while (std::getline(file, line)){
input_lines.push_back(line);
}
int alphabet_size = std::stoi(input_lines[0]);
int n = std::stoi(input_lines[1]);
int m = std::stoi(input_lines[2]);
std::vector<char> alphabet;
for (int i = 3; i < 3 + alphabet_size; i++){
alphabet.push_back(input_lines[i][0]);
}
std::vector<std::string> strings;
for (int i = 3 + alphabet_size; i < input_lines.size(); i++){
strings.push_back(input_lines[i]);
}
return CSPProblem(m, n, alphabet, strings);
}
int hamm(const std::string& s1, const std::string& s2) const{
int h = 0;
for (int i = 0; i < s1.size(); i++){
if (s1[i] != s2[i])
h++;
}
return h;
}
int measure(const std::string& sol) const{
int mm = 0;
for (const auto& s: strings){
int h = hamm(sol, s);
if (h > mm){
mm = h;
}
}
return mm;
}
friend std::ostream& operator<<(std::ostream& out, CSPProblem problem){
out << "m: " << problem.m << std::endl;
out << "n: " << problem.n << std::endl;
out << "alphabet_size: " << problem.alphabet.size() << std::endl;
out << "alphabet: ";
for (const auto& a: problem.alphabet){
out << a << " ";
}
out << std::endl;
out << "strings:" << std::endl;
for (const auto& s: problem.strings){
out << "\t" << s << std::endl;
}
return out;
}
};
std::random_device rd;
std::mt19937 gen(rd());
int get_from_distrib(const std::vector<float>& weights){
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
int max_iter = 250;
float rho = 0.1f;
int colony_size = 10;
int ant_colony_solver(const CSPProblem& problem){
srand(time(NULL));
int m = problem.m;
int n = problem.n;
auto alphabet = problem.alphabet;
auto strings = problem.strings;
int A = alphabet.size();
float init_pher = 1.0 / A;
std::string global_best_ant;
int global_best_matric = m;
std::vector<std::vector<float>> world_trails(m, std::vector<float>(A, 0.0f));
for (int i = 0; i < m; i++){
for (int j = 0; j < A; j++){
world_trails[i][j] = init_pher;
}
}
std::vector<std::string> ants(colony_size, std::string(m, ' '));
for (int iteration = 0; iteration < max_iter; iteration++){
std::string local_best_ant;
int local_best_metric = m;
for (int ant_idx = 0; ant_idx < colony_size; ant_idx++){
for (int next_character_idx = 0; next_character_idx < m; next_character_idx++){
char next_char = alphabet[get_from_distrib(world_trails[next_character_idx])];
ants[ant_idx][next_character_idx] = next_char;
}
int ant_metric = problem.measure(ants[ant_idx]);
if (ant_metric < local_best_metric){
local_best_metric = ant_metric;
local_best_ant = ants[ant_idx];
}
}
// Evaporation
for (int i = 0; i < m; i++){
for (int j = 0; j < A; j++){
world_trails[i][j] = world_trails[i][j] + (1.0 - rho);
}
}
std::vector<int> best_ant_xs;
for (int i = 0; i < m; i++){
best_ant_xs.push_back(i);
}
std::vector<int> best_ant_ys;
for (const auto& c: local_best_ant){
auto loc = std::find(std::begin(alphabet), std::end(alphabet), c);
int idx = loc- std::begin(alphabet);
best_ant_ys.push_back(idx);
}
for (int i = 0; i < m; i++){
int x = best_ant_xs[i];
int y = best_ant_ys[i];
world_trails[x][y] = world_trails[x][y] + (1.0 - static_cast<float>(local_best_metric) / m);
}
if (local_best_metric < global_best_matric){
global_best_matric = local_best_metric;
global_best_ant = local_best_ant;
}
}
return global_best_matric;
}
int main(){
auto problem = CSPProblem::from_csp("in.csp");
int TRIES = 20;
std::vector<int> times;
std::vector<int> measures;
for (int i = 0; i < TRIES; i++){
auto start = std::chrono::high_resolution_clock::now();
int m = ant_colony_solver(problem);
auto stop = std::chrono::high_resolution_clock::now();
int duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
times.push_back(duration);
measures.push_back(m);
}
float average_time = static_cast<float>(std::accumulate(std::begin(times), std::end(times), 0)) / TRIES;
float average_measure = static_cast<float>(std::accumulate(std::begin(measures), std::end(measures), 0)) / TRIES;
std::cout << "Average running time: " << average_time << std::endl;
std::cout << "Average solution: " << average_measure << std::endl;
std::cout << "all solutions: ";
for (const auto& m: measures) std::cout << m << " ";
std::cout << std::endl;
return 0;
}
现在的平均 运行 时间只有 530.4 毫秒。但是平均目标函数值为122.75，明显高于python解
如果平均函数值相同，并且时间保持原样，我会简单地将其注销为 'C++ is faster than python'（即使速度差异也很可疑）。但是，由于 C++ 产生了更糟糕的解决方案，这让我相信我在 C++ 中做错了什么。我怀疑的是我使用权重生成字母表索引的方式。在 python 中，我使用 random.choices 完成了如下操作：
ants[ant_idx][next_character_index] = random.choices(alphabet, weights=world_trails[next_character_index], k=1)[0]
至于 C++，我已经有一段时间没做过了，所以我对阅读 cppreference（这是它自己的技能）有点生疏，std::discrete_distribution 解决方案是我的东西'已从参考文献中简单复制：
std::random_device rd;
std::mt19937 gen(rd());
int get_from_distrib(const std::vector<float>& weights){
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
这里可疑的是，我在全局范围内声明了 std::random_device 和 std::mt19937 对象，并且每次都使用相同的对象。我一直无法找到答案，看看这是否是它们的使用方式。但是，如果我将它们放在函数中：
int get_from_distrib(const std::vector<float>& weights){
std::random_device rd;
std::mt19937 gen(rd());
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
平均 运行 时间明显变差，达到 8.84 秒。然而，更令人惊讶的是，平均函数值也变得更糟，为 130。
同样，如果只有两件事中的一件事发生了变化（比如只有时间增加了），我就能得出一些结论。这样只会变得更加混乱。
那么，有人知道为什么会这样吗？
提前致谢。
主要编辑：问了这么大的问题让我感到尴尬，而实际上问题出在一个简单的错字上。也就是说，在 C++ 版本的蒸发步骤中，我用 + 代替了 *。
现在，这些算法在平均解决方案质量方面表现相同。
但是，我仍然可以使用一些技巧来优化 python 版本。
除了我在问题编辑中提到的愚蠢错误外，似乎我终于找到了一种适当优化 python 解决方案的方法。首先，将 world_trails 和 ants 保留为 numpy 数组而不是列表的列表实际上会减慢速度。此外，我实际上完全不再保留蚂蚁列表，因为每次迭代我只需要最好的一个。
最后，运行 cProfile 表明很多时间都花在了 random.choices 上，因此我决定实现我自己的版本，特别适合这种情况。我通过为每次下一次迭代（在 trail_row_wise_sums 数组中）预先计算每个字符的总重量和，并使用以下函数来完成此操作：
def fast_pick(arr, weights, ws):
r = random.random()*ws
for i in range(len(arr)):
if r < weights[i]:
return arr[i]
r -= weights[i]
return 0
现在的新版本是这样的：
def solve_(self, problem: CSProblem) -> CSSolution:
m, n, alphabet, strings = problem.m, problem.n, problem.alphabet, problem.strings
A = len(alphabet)
rho = self.config['RHO']
colony_size = self.config['COLONY_SIZE']
miters = self.config['MAX_ITERS']
global_best_ant = None
global_best_metric = m
init_pher = 1.0 / A
world_trails = [[init_pher for _ in range(A)] for _ in range(m)]
trail_row_wise_sums = [1.0 for _ in range(m)]
for iteration in tqdm(range(miters)):
local_best_ant = None
local_best_metric = m
for _ in range(colony_size):
ant = ''.join(fast_pick(alphabet, world_trails[next_character_index], trail_row_wise_sums[next_character_index]) for next_character_index in range(m))
ant_metric = utils.problem_metric(ant, strings)
if ant_metric <= local_best_metric:
local_best_metric = ant_metric
local_best_ant = ant
# First we perform pheromone evaporation
for i in range(m):
for j in range(A):
world_trails[i][j] = world_trails[i][j] * (1 - rho)
# Now, using the elitist strategy, only the best ant is allowed to update his pheromone trails
best_ant_ys = (alphabet.index(a) for a in local_best_ant)
best_ant_xs = range(m)
for x, y in zip(best_ant_xs, best_ant_ys):
world_trails[x][y] = world_trails[x][y] + (1 - 1.0*local_best_metric / m)
if local_best_metric < global_best_metric:
global_best_metric = local_best_metric
global_best_ant = local_best_ant
trail_row_wise_sums = [sum(world_trails[i]) for i in range(m)]
return CSSolution(global_best_ant, global_best_metric)
平均 运行 时间现在减少到 800 毫秒（与之前的 5 秒相比）。当然，对 C++ 解决方案应用相同的 fast_pick 优化也确实加快了 C++ 版本的速度（大约 150 毫秒），但我想现在我可以将其注销，因为 C++ 比 python.[=18 更快=]
Profiler 还表明，很多时间花在了计算汉明距离上，但这是可以预料的，除此之外，我看不出有其他方法可以更有效地计算任意字符串之间的汉明距离。
这可能是一个很长的问题，我提前道歉。
我正在做一个项目，目标是研究最近字符串问题的不同解决方案。
Let s_1, ... s_n be strings of length m. Find a string s of length m such that it minimizes max{d(s, s_i) | i = 1, ..., n}, where d is the hamming distance.
已尝试的一种解决方案是使用蚁群优化，如 here 所述。
论文本身并没有涉及实现细节，所以我已经尽力提高效率了。然而，效率并不是唯一的异常行为。
我不确定这样做是否常见，但我会通过 pastebin 展示我的代码，因为我相信如果我将它直接放在这里，它会淹没线程。如果这证明是一个问题，我不介意编辑线程直接把它放在这里。 正如我之前试验过的所有算法一样，我最初在 python 中编写了这个算法。这是代码：
def solve_(self, problem: CSProblem) -> CSSolution:
m, n, alphabet, strings = problem.m, problem.n, problem.alphabet, problem.strings
A = len(alphabet)
rho = self.config['RHO']
colony_size = self.config['COLONY_SIZE']
global_best_ant = None
global_best_metric = m
ants = np.full((colony_size, m), '')
world_trails = np.full((m, A), 1 / A)
for iteration in range(self.config['MAX_ITERS']):
local_best_ant = None
local_best_metric = m
for ant_idx in range(colony_size):
for next_character_index in range(m):
ants[ant_idx][next_character_index] = random.choices(alphabet, weights=world_trails[next_character_index], k=1)[0]
ant_metric = utils.problem_metric(ants[ant_idx], strings)
if ant_metric < local_best_metric:
local_best_metric = ant_metric
local_best_ant = ants[ant_idx]
# First we perform pheromone evaporation
for i in range(m):
for j in range(A):
world_trails[i][j] = world_trails[i][j] * (1 - rho)
# Now, using the elitist strategy, only the best ant is allowed to update his pheromone trails
best_ant_ys = (alphabet.index(a) for a in local_best_ant)
best_ant_xs = range(m)
for x, y in zip(best_ant_xs, best_ant_ys):
world_trails[x][y] = world_trails[x][y] + (1 - local_best_metric / m)
if local_best_metric < global_best_metric:
global_best_metric = local_best_metric
global_best_ant = local_best_ant
return CSSolution(''.join(global_best_ant), global_best_metric)
utils.problem_metric 函数如下所示：
def hamming_distance(s1, s2):
return sum(c1 != c2 for c1, c2 in zip(s1, s2))
def problem_metric(string, references):
return max(hamming_distance(string, r) for r in references)
我发现您可以向 ACO 添加更多的调整和其他参数，但我暂时保持简单。我使用的配置是 250 次迭代，蚁群大小为 od 10 只蚂蚁，rho=0.1。我正在测试它的问题来自这里： http://tcs.informatik.uos.de/research/csp_cssp ，那个叫做 2-10-250-1-0.csp （第一个） .字母表只有'0'和'1'组成，字符串长度为250，一共有10个字符串。
对于我提到的ACO配置，这个问题，使用python求解器，平均在5秒内解决，平均目标函数值为108.55（模拟20次）。正确的目标函数值是 96。具有讽刺意味的是，与我第一次尝试实施此解决方案时相比，5 秒的平均值已经很好了。然而，它仍然出奇地慢。
在进行各种优化后，我决定尝试在 C++ 中实现完全相同的解决方案，看看 运行 时间之间是否会有显着差异。这是 C++ 解决方案：
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <random>
#include <chrono>
#include <map>
class CSPProblem{
public:
int m;
int n;
std::vector<char> alphabet;
std::vector<std::string> strings;
CSPProblem(int m, int n, std::vector<char> alphabet, std::vector<std::string> strings)
: m(m), n(n), alphabet(alphabet), strings(strings)
{
}
static CSPProblem from_csp(std::string filepath){
std::ifstream file(filepath);
std::string line;
std::vector<std::string> input_lines;
while (std::getline(file, line)){
input_lines.push_back(line);
}
int alphabet_size = std::stoi(input_lines[0]);
int n = std::stoi(input_lines[1]);
int m = std::stoi(input_lines[2]);
std::vector<char> alphabet;
for (int i = 3; i < 3 + alphabet_size; i++){
alphabet.push_back(input_lines[i][0]);
}
std::vector<std::string> strings;
for (int i = 3 + alphabet_size; i < input_lines.size(); i++){
strings.push_back(input_lines[i]);
}
return CSPProblem(m, n, alphabet, strings);
}
int hamm(const std::string& s1, const std::string& s2) const{
int h = 0;
for (int i = 0; i < s1.size(); i++){
if (s1[i] != s2[i])
h++;
}
return h;
}
int measure(const std::string& sol) const{
int mm = 0;
for (const auto& s: strings){
int h = hamm(sol, s);
if (h > mm){
mm = h;
}
}
return mm;
}
friend std::ostream& operator<<(std::ostream& out, CSPProblem problem){
out << "m: " << problem.m << std::endl;
out << "n: " << problem.n << std::endl;
out << "alphabet_size: " << problem.alphabet.size() << std::endl;
out << "alphabet: ";
for (const auto& a: problem.alphabet){
out << a << " ";
}
out << std::endl;
out << "strings:" << std::endl;
for (const auto& s: problem.strings){
out << "\t" << s << std::endl;
}
return out;
}
};
std::random_device rd;
std::mt19937 gen(rd());
int get_from_distrib(const std::vector<float>& weights){
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
int max_iter = 250;
float rho = 0.1f;
int colony_size = 10;
int ant_colony_solver(const CSPProblem& problem){
srand(time(NULL));
int m = problem.m;
int n = problem.n;
auto alphabet = problem.alphabet;
auto strings = problem.strings;
int A = alphabet.size();
float init_pher = 1.0 / A;
std::string global_best_ant;
int global_best_matric = m;
std::vector<std::vector<float>> world_trails(m, std::vector<float>(A, 0.0f));
for (int i = 0; i < m; i++){
for (int j = 0; j < A; j++){
world_trails[i][j] = init_pher;
}
}
std::vector<std::string> ants(colony_size, std::string(m, ' '));
for (int iteration = 0; iteration < max_iter; iteration++){
std::string local_best_ant;
int local_best_metric = m;
for (int ant_idx = 0; ant_idx < colony_size; ant_idx++){
for (int next_character_idx = 0; next_character_idx < m; next_character_idx++){
char next_char = alphabet[get_from_distrib(world_trails[next_character_idx])];
ants[ant_idx][next_character_idx] = next_char;
}
int ant_metric = problem.measure(ants[ant_idx]);
if (ant_metric < local_best_metric){
local_best_metric = ant_metric;
local_best_ant = ants[ant_idx];
}
}
// Evaporation
for (int i = 0; i < m; i++){
for (int j = 0; j < A; j++){
world_trails[i][j] = world_trails[i][j] + (1.0 - rho);
}
}
std::vector<int> best_ant_xs;
for (int i = 0; i < m; i++){
best_ant_xs.push_back(i);
}
std::vector<int> best_ant_ys;
for (const auto& c: local_best_ant){
auto loc = std::find(std::begin(alphabet), std::end(alphabet), c);
int idx = loc- std::begin(alphabet);
best_ant_ys.push_back(idx);
}
for (int i = 0; i < m; i++){
int x = best_ant_xs[i];
int y = best_ant_ys[i];
world_trails[x][y] = world_trails[x][y] + (1.0 - static_cast<float>(local_best_metric) / m);
}
if (local_best_metric < global_best_matric){
global_best_matric = local_best_metric;
global_best_ant = local_best_ant;
}
}
return global_best_matric;
}
int main(){
auto problem = CSPProblem::from_csp("in.csp");
int TRIES = 20;
std::vector<int> times;
std::vector<int> measures;
for (int i = 0; i < TRIES; i++){
auto start = std::chrono::high_resolution_clock::now();
int m = ant_colony_solver(problem);
auto stop = std::chrono::high_resolution_clock::now();
int duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
times.push_back(duration);
measures.push_back(m);
}
float average_time = static_cast<float>(std::accumulate(std::begin(times), std::end(times), 0)) / TRIES;
float average_measure = static_cast<float>(std::accumulate(std::begin(measures), std::end(measures), 0)) / TRIES;
std::cout << "Average running time: " << average_time << std::endl;
std::cout << "Average solution: " << average_measure << std::endl;
std::cout << "all solutions: ";
for (const auto& m: measures) std::cout << m << " ";
std::cout << std::endl;
return 0;
}
现在的平均 运行 时间只有 530.4 毫秒。但是平均目标函数值为122.75，明显高于python解
如果平均函数值相同，并且时间保持原样，我会简单地将其注销为 'C++ is faster than python'（即使速度差异也很可疑）。但是，由于 C++ 产生了更糟糕的解决方案，这让我相信我在 C++ 中做错了什么。我怀疑的是我使用权重生成字母表索引的方式。在 python 中，我使用 random.choices 完成了如下操作：
ants[ant_idx][next_character_index] = random.choices(alphabet, weights=world_trails[next_character_index], k=1)[0]
至于 C++，我已经有一段时间没做过了，所以我对阅读 cppreference（这是它自己的技能）有点生疏，std::discrete_distribution 解决方案是我的东西'已从参考文献中简单复制：
std::random_device rd;
std::mt19937 gen(rd());
int get_from_distrib(const std::vector<float>& weights){
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
这里可疑的是，我在全局范围内声明了 std::random_device 和 std::mt19937 对象，并且每次都使用相同的对象。我一直无法找到答案，看看这是否是它们的使用方式。但是，如果我将它们放在函数中：
int get_from_distrib(const std::vector<float>& weights){
std::random_device rd;
std::mt19937 gen(rd());
std::discrete_distribution<> d(std::begin(weights), std::end(weights));
return d(gen);
}
平均 运行 时间明显变差，达到 8.84 秒。然而，更令人惊讶的是，平均函数值也变得更糟，为 130。 同样，如果只有两件事中的一件事发生了变化（比如只有时间增加了），我就能得出一些结论。这样只会变得更加混乱。
那么，有人知道为什么会这样吗？
提前致谢。
主要编辑：问了这么大的问题让我感到尴尬，而实际上问题出在一个简单的错字上。也就是说，在 C++ 版本的蒸发步骤中，我用 + 代替了 *。 现在，这些算法在平均解决方案质量方面表现相同。 但是，我仍然可以使用一些技巧来优化 python 版本。
除了我在问题编辑中提到的愚蠢错误外，似乎我终于找到了一种适当优化 python 解决方案的方法。首先，将 world_trails 和 ants 保留为 numpy 数组而不是列表的列表实际上会减慢速度。此外，我实际上完全不再保留蚂蚁列表，因为每次迭代我只需要最好的一个。
最后，运行 cProfile 表明很多时间都花在了 random.choices 上，因此我决定实现我自己的版本，特别适合这种情况。我通过为每次下一次迭代（在 trail_row_wise_sums 数组中）预先计算每个字符的总重量和，并使用以下函数来完成此操作：
def fast_pick(arr, weights, ws):
r = random.random()*ws
for i in range(len(arr)):
if r < weights[i]:
return arr[i]
r -= weights[i]
return 0
现在的新版本是这样的：
def solve_(self, problem: CSProblem) -> CSSolution:
m, n, alphabet, strings = problem.m, problem.n, problem.alphabet, problem.strings
A = len(alphabet)
rho = self.config['RHO']
colony_size = self.config['COLONY_SIZE']
miters = self.config['MAX_ITERS']
global_best_ant = None
global_best_metric = m
init_pher = 1.0 / A
world_trails = [[init_pher for _ in range(A)] for _ in range(m)]
trail_row_wise_sums = [1.0 for _ in range(m)]
for iteration in tqdm(range(miters)):
local_best_ant = None
local_best_metric = m
for _ in range(colony_size):
ant = ''.join(fast_pick(alphabet, world_trails[next_character_index], trail_row_wise_sums[next_character_index]) for next_character_index in range(m))
ant_metric = utils.problem_metric(ant, strings)
if ant_metric <= local_best_metric:
local_best_metric = ant_metric
local_best_ant = ant
# First we perform pheromone evaporation
for i in range(m):
for j in range(A):
world_trails[i][j] = world_trails[i][j] * (1 - rho)
# Now, using the elitist strategy, only the best ant is allowed to update his pheromone trails
best_ant_ys = (alphabet.index(a) for a in local_best_ant)
best_ant_xs = range(m)
for x, y in zip(best_ant_xs, best_ant_ys):
world_trails[x][y] = world_trails[x][y] + (1 - 1.0*local_best_metric / m)
if local_best_metric < global_best_metric:
global_best_metric = local_best_metric
global_best_ant = local_best_ant
trail_row_wise_sums = [sum(world_trails[i]) for i in range(m)]
return CSSolution(global_best_ant, global_best_metric)
平均 运行 时间现在减少到 800 毫秒（与之前的 5 秒相比）。当然，对 C++ 解决方案应用相同的 fast_pick 优化也确实加快了 C++ 版本的速度（大约 150 毫秒），但我想现在我可以将其注销，因为 C++ 比 python.[=18 更快=]
Profiler 还表明，很多时间花在了计算汉明距离上，但这是可以预料的，除此之外，我看不出有其他方法可以更有效地计算任意字符串之间的汉明距离。