Imperialist Competitive Algorithm.md · 伍小南18/Imperialist Competitive Algorithm_Cpp

# Imperialist Competitive Algorithm

### Reference

https://blog.csdn.net/u011835903/article/details/108517210

https://blog.csdn.net/zhouhaomy/article/details/105116701

### Spec

工程设计中最优化问题（optimalization problem）的一般提法是要选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。因此，最优化问题通常可以表示为数学规划形式的问题。进行工程优化设计时，应将工程设计问题用上述形式表示成数学问题，再用最优化的方法求解。

最优化算法包括精确算法与启发式算法，后者又有个体启发（局部最优）与群体智能。ICA就是一种群体智能优化搜索算法。

ICA是一个N维优化算法。与PSO（粒子群算法）相比，ICA收敛速度快、收敛精度高，具有较强的全局收敛性；但由于竞争过程中帝国合并以及帝国覆灭使ICA的帝国个数不断减少，导致群体多样性降低，算法的全局＂勘探＂能力受影响，易出现＂早熟＂现象。

### Parameter

初始国家数目$N_{pop}$，帝国主义国家数$N_{imp}$和殖民地数$N_{col}$，帝国竞争年限$Time$，帝国主义国家势力(代价函数$f_{n}$、殖民地影响因子$ξ$)，同化系数($β,γ$)。

### Process

![image-20220104104520570](C:\Users\wrnth\AppData\Roaming\Typora\typora-user-images\image-20220104104520570.png)

### Class & Struct

| Name            | Type          | Spec                                                         |
| --------------- | ------------- | ------------------------------------------------------------ |
| Country_Profile | struct        | 重载<，==；含有map Country，double cost                      |
| Country         | map<int, int> | key为country的维度序号，在ParamIndex中按序标号；value为ParamVal中随机抽取的值 |
|                 |               | country是一个N维的map，记录了该国家N维的数据                 |
| Imper_Profile   | struct        | 重载<；Country_Profile Imper，list ColonyList, TotalCost     |

### Function

| 步骤                       | 函数                        | 具体操作                                                     | 结果                                                         |
| -------------------------- | --------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 创建类                     | ICA(...)                    |                                                              | 需要读文件得value；序号默认；                                |
| 计算殖民地cost             | ColonyCostCalc()            | 计算帝国集团的每个殖民地的cost                               |                                                              |
| 计算cost                   | Cost(Country)               | 计算国家的cost                                               | 需要具体实现公式，目前采用的是Cost=sum(1/value)              |
| 初始化                     | InitializeCountries()       | 按照顺序标号每一个国家，并依照参数表随机生成势力值；根据国家势力值计算满足条件（<InAcceptableCostVal）的cost，结果压入m_CountryList；国家按势力排序，前几个国家变成帝国，循环给每个帝国一个殖民地 | m_CountryList有了所有的国家                                  |
| 初始化帝国                 | InitializeImpires()         | 前几个国家变成帝国，循环把殖民地压入帝国集团的ColonyList     | 前m_ImpNum个国家出m_CountryList入m_ImperList，并依次瓜分殖民地 |
| 吸收殖民地                 | Assimilate_Clony_to_Imper() | 对帝国的每个殖民地，随机在N维（可重复）方向上向帝国靠近      | 某些维度总计靠近Country.size()次                             |
| 殖民地革命                 | Doing_Revolution()          | 革命几率*帝国势力数向下取整即为革命数x。随机挑选一个帝国的一个殖民地，其各维度随机变化 | 随机x个殖民地，一个殖民地随机ColonyList.size()次             |
| 判断cost，交换殖民地与帝国 | Colony_Imper_swap()         | 对每一个帝国势力，对该势力的每个殖民地，若殖民地的cost<帝国的cost，则交换殖民地势力与帝国势力 |                                                              |
|                            |                             |                                                              |                                                              |
| 计算帝国集团成本，排序     | Eliminate_Weakest_Imper()   | 帝国势力排序，将最弱帝国的第一个殖民地（若没有殖民地，则将他自己）给最强帝国 | 不知为何，此算法中一直没有收敛，帝国数量不会变化             |
| 帝国竞争殖民地             | 👆                           | 👆                                                            |                                                              |
| 分割没有殖民地的帝国       | 👆                           | 👆                                                            |                                                              |
| 合并帝国集团               | Merge_Similar_Impers()      | 对每一个帝国势力，找到其之后与其cost相等的帝国势力，殖民后者与后者的殖民地 | 由于采用了double类型的value，考虑x±1≈x，即误差在1以内也算相等 |
|                            |                             |                                                              |                                                              |
|                            |                             |                                                              |                                                              |

cost计算函数

```C++
typedef function<double(map<int,int>)> CostfunType;
CostfunType Cost;//ICA类中的函数
void SetCost(const CostfunType & CostFunc){ Cost = CostFunc;}
Cost(itCol->Country);//h
```

按照给出的公式
$$
Cost=f(p_1,\ p_2,\ ...,\ p_N)\\
TotalCost=Cost(imprialist)+\xi mean\{Cost(colonies)\}
$$
一个帝国在没有殖民地的时候Cost会明显减小，这是不合理的，会导致瓜分完最弱帝国的殖民地之后，最弱帝国变成了强大的帝国，又把殖民地抢回去。

改为
$$
Cost=f(p_1,\ p_2,\ ...,\ p_N)\\
TotalCost=(1-\xi )Cost(imprialist)+\xi mean\{Cost(colonies)\}
$$
更合理。

## Usage

具体查看Readme。

## BUG

1. 在帝国较少时似乎不会收敛（帝国3%，前3000cycles），帝国总数没有变化，总是周期性的后面的弱小国家轮换，但殖民地数量没有发生减小；在帝国较多时收敛较快。

> 需要真正测试的数据集，并了解怎样算合理的收敛速度。

2. ICA算法的cost计算公式不合理——占据更多殖民地的帝国理应更强大，也即cost更小；但实际上吞并了殖民地后帝国反而更弱了，只有后续吸收才有可能变强，这就导致了强大的帝国可能刚吸收就变成了弱小的帝国，导致“殖民地踢皮球”现象。

> 考虑”改算法为比例分割而非直接相加“；
    >
    > 考虑吸收最弱帝国的某一殖民地（不是最弱）；

## 待改进

1. 关于测试样例数据类型的兼容（目前适配double，准备改成Template）；如果要求变化的数值只能在初始规定的集合中取，那么需要对应地修改随机函数的取值范围，让函数在给定的数据集上随机取值

2. 对随机算法的优化，包括随机抽样、随机吸收、革命

3. 增加结果画图

> 已实现，使用python，源代码在根目录下"plot.py"，已打包

4. 实现标准化代价计算

5. 实现势力值重复判断（目前默认按不判断）

伍小南18/Imperialist Competitive Algorithm_Cpp

简介

发行版

贡献者

语言

近期动态

伍小南18/Imperialist Competitive Algorithm_Cpp .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

伍小南18/Imperialist Competitive Algorithm_Cpp