Chap I 人工智能的起源与历史
Abstract
人工智能最早存在三大学派, 分别是进化学派, 类推学派, 贝叶斯学派, 三种主义, 分别是符号主义, 联结主义, 行为主义. 当今的人工智能都起源于此.
1. 1 主流学派实例解释
1. 1. 1 进化学派
Note
因为进化算法很常用, 所以这里多介绍一点.
问题引入: 0-1 背包问题
假设你有三件物品, 其价值为[60, 100, 120], 其重量为[10, 20, 30]. 已知你的背包容量为50, 请选择物品放入背包, 使总价值最大.
贪心法:
这里的思路是计算出每个物品每一重量的价值, 按序选择. 这一算法显然无法达到最优解
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义物品结构体
struct Item {
int value;
int weight;
double ratio;
// 构造函数
Item(int v, int w) {
value = v;
weight = w;
ratio = (double)v / w;
}
};
// 比较函数：按单位价值从大到小排序
bool compare(Item a, Item b) {
return a.ratio > b.ratio;
}
// 贪心算法函数
int greedyKnapsack(vector<int>& values, vector<int>& weights, int capacity) {
vector<Item> items;
int n = values.size();
// 构造物品列表
for (int i = 0; i < n; ++i) {
items.push_back(Item(values[i], weights[i]));
}
// 排序
sort(items.begin(), items.end(), compare);
int totalValue = 0;
vector<pair<int, int>> chosen;
for (int i = 0; i < n; ++i) {
if (items[i].weight <= capacity) {
capacity -= items[i].weight;
totalValue += items[i].value;
chosen.push_back({items[i].value, items[i].weight});
}
}
// 输出选择的物品
cout << "选择的物品（价值, 重量）: ";
for (auto& p : chosen) {
cout << "(" << p.first << ", " << p.second << ") ";
}
cout << endl;
return totalValue;
}
// 主函数测试
int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50;
int result = greedyKnapsack(values, weights, capacity);
cout << "贪心法获得的最大价值: " << result << endl;
return 0;
}
|
运行结果
| 选择的物品（价值, 重量）: (60, 10) (100, 20)
贪心法获得的最大价值: 160
|
动态规划:
这里给出二维 DP 版本
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 动态规划解决 0-1 背包问题
int dpKnapsack(const vector<int>& values, const vector<int>& weights, int capacity) {
int n = values.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// 填表
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= capacity; ++w) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// 主函数测试
int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50;
int result = dpKnapsack(values, weights, capacity);
cout << "动态规划获得的最大价值: " << result << endl;
return 0;
}
|
运行结果
上述两种方案都是传统算法. 贪心法的缺点很明显, 只能得到局部最优解; 动态规划如果了解过, 在数据规模极大的情况下会产生极高的空间复杂度, 并且不适用于约束条件极其复杂的情况.
而进化学派的代表算法, 进化算法很好的解决了这一点.
进化算法综合了上述两种方案的优点, 得到一种折中的方案. 也就是, 虽然不保证结果一定最优, 但是伴随迭代次数增多, 会逼近于最优解; 虽然时间复杂度相较于传统算法更大, 但是空间可控, 并且很容易添加复杂约束.
换言之, 进化学派利用生物学中的进化思想, 在不断地迭代中找到最优解或者近似最优解.
代码实现:
| #include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
// 参数
const int POP_SIZE = 100; // 种群大小
const int GENERATIONS = 100; // 迭代次数
const double CROSS_RATE = 0.7; // 交叉率
const double MUTATE_RATE = 0.01; // 变异率
// 问题数据
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50;
int n = values.size();
// 染色体类型：一个二进制向量
typedef vector<int> Chromosome;
// 适应度函数：如果超重则为0
int fitness(const Chromosome& chromo) {
int total_value = 0, total_weight = 0;
for (int i = 0; i < n; ++i) {
if (chromo[i]) {
total_value += values[i];
total_weight += weights[i];
}
}
return (total_weight <= capacity) ? total_value : 0;
}
// 初始化随机染色体
Chromosome random_chromosome() {
Chromosome c(n);
for (int i = 0; i < n; ++i)
c[i] = rand() % 2;
return c;
}
// 单点交叉
Chromosome crossover(const Chromosome& p1, const Chromosome& p2) {
Chromosome child(n);
int point = rand() % n;
for (int i = 0; i < n; ++i)
child[i] = (i < point) ? p1[i] : p2[i];
return child;
}
// 变异
void mutate(Chromosome& chromo) {
for (int i = 0; i < n; ++i) {
if ((double)rand() / RAND_MAX < MUTATE_RATE)
chromo[i] = 1 - chromo[i];
}
}
int main() {
srand(time(0));
// Step 1: 初始化种群
vector<Chromosome> population;
for (int i = 0; i < POP_SIZE; ++i)
population.push_back(random_chromosome());
Chromosome best;
int best_fit = 0;
// Step 2: 演化
for (int gen = 0; gen < GENERATIONS; ++gen) {
// 计算适应度
vector<pair<int, Chromosome>> fitness_pool;
for (auto& c : population)
fitness_pool.push_back({fitness(c), c});
// 保留最优个体
sort(fitness_pool.rbegin(), fitness_pool.rend());
if (fitness_pool[0].first > best_fit) {
best_fit = fitness_pool[0].first;
best = fitness_pool[0].second;
}
// Step 3: 选择 + 交叉 + 变异生成新种群
vector<Chromosome> new_population;
for (int i = 0; i < POP_SIZE; ++i) {
// 轮盘赌选择两个父母
Chromosome p1 = fitness_pool[rand() % (POP_SIZE / 2)].second;
Chromosome p2 = fitness_pool[rand() % (POP_SIZE / 2)].second;
Chromosome child = (double)rand() / RAND_MAX < CROSS_RATE ? crossover(p1, p2) : p1;
mutate(child);
new_population.push_back(child);
}
population = new_population;
}
// 输出结果
cout << "遗传算法最优解：" << best_fit << endl;
cout << "选择的物品：";
for (int i = 0; i < n; ++i) {
if (best[i])
cout << "(value=" << values[i] << ", weight=" << weights[i] << ") ";
}
cout << endl;
return 0;
}
|
运行结果
| 遗传算法最优解：220
选择的物品：(value=100, weight=20) (value=120, weight=30)
|
1. 1. 2 类推学派
将旧问题与新问题类比, 找到"相似情景".
例如, 对下面这一组映射
\[
\{x,y,z\}\longrightarrow \{y,z,x\}
\]
当我们再次给定一组数据 \(\{1,2,3\}\), 自动映射为 \(\{2,3,1\}\).
当然, 上述例子并不够准确. 因为类推推理在表征查找这一步要灵活很多.
也就是说, 解决新问题就是将新问题类比映射到旧问题上.
1. 1. 3 贝叶斯学派
基于贝叶斯定理而成. 这一学派实际上提出了四个假设:
- 学习就是概率的更新
- 决策/推理始终是不确定的, 这一过程仅仅只是可信度, 概率的加强
- 主观信念的映射是概率
- 没有纯粹的客观模型, 所有模型都有先验假设
学习过程就是对不确定概率的不断更新.
1. 2 三种主义的简单解释
- 符号主义: 智能 = 符号操作 + 规则推理
- 联结主义: 智能 = 神经元连接与权重调整
- 行为主义: 智能 = 刺激与反应之间的学习行为
其中, 联结主义是今天人工智能大模型的基础.
1. 3 幸存者偏差
这是今天 AI 很常见的一个问题. 简单来说, 就是问题考虑不全面, 没有给足够宽泛的数据进行训练.
最经典的就是二战加固飞机装甲这一例子. 我们知道, 当时大部分盟军指挥官都认为应当加固弹孔密集区, 因为这些部分被打的最多. 这就是样例不全面导致的误判, 因为他们没有考虑到被击落的飞机.
这种"被击落的飞机"就是我们在制作数据集训练的时候经常犯的错误, 也就造成了今天常见的 AI 幸存者偏差问题.