【遗传算法】Genetic algorithms (GAs) 遗传算法原理入门与应用代码

目录

1 遗传算法        

2 遗传算法的基本步骤

3 Python示例

4 遗传算法解决TSP(旅行商问题) 


1 遗传算法        

        遗传算法是一种优化搜索算法,模拟自然选择和遗传机制来寻找问题的最优解。这种算法的设计灵感来自于达尔文的进化论和遗传学的基本原理。遗传算法通常用于解决优化问题,其中需要找到某个问题的最优解或近似最优解。

2 遗传算法的基本步骤

  1. 初始化种群(Population Initialization): 随机生成一组个体(解决方案)组成的初始群体。每个个体通常由染色体表示,染色体上的基因表示问题的解。

  2. 适应度评估(Fitness Evaluation): 对每个个体计算适应度,即解决方案的优劣程度。适应度函数根据问题的性质而定,它用于量化个体的质量。

  3. 选择(Selection): 选择适应度较高的个体,作为下一代种群的父代。通常,适应度较高的个体被选中的概率较大,模拟了自然选择的过程。

  4. 交叉(Crossover): 通过交叉操作,从父代中生成新的个体。这模拟了基因的交叉过程,将两个父代的染色体组合生成新的染色体。

  5. 变异(Mutation): 对新生成的个体进行变异操作,以引入一些随机性。变异有助于维持种群的多样性,避免陷入局部最优解。

  6. 替换(Replacement): 用新生成的个体替代原始种群中适应度较低的个体。这是为了确保种群中的优质个体得以保留。

  7. 重复迭代(Iteration): 重复执行上述步骤,直到满足停止条件。停止条件可以是达到预定的迭代次数,找到满意的解,或者适应度已经足够高。

3 Python示例

下面是一个简单的Python示例,演示了如何实现一个基本的遗传算法来解决一个简单的优化问题:

import random

# 1. 初始化种群
def initialize_population(population_size, chromosome_length):
    return [[random.randint(0, 1) for _ in range(chromosome_length)] for _ in range(population_size)]

# 2. 适应度评估
def fitness(individual):
    return sum(individual)

# 3. 选择
def selection(population):
    population_size = len(population)
    fitness_scores = [fitness(individual) for individual in population]
    total_fitness = sum(fitness_scores)
    probabilities = [score / total_fitness for score in fitness_scores]
    selected_indices = random.choices(range(population_size), weights=probabilities, k=population_size)
    return [population[i] for i in selected_indices]

# 4. 交叉
def crossover(parent1, parent2):
    crossover_point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

# 5. 变异
def mutation(individual, mutation_rate):
    mutated_individual = individual[:]
    for i in range(len(mutated_individual)):
        if random.random() < mutation_rate:
            mutated_individual[i] = 1 - mutated_individual[i]
    return mutated_individual

# 6. 替换
def replacement(population, offspring):
    return population + offspring

# 7. 遗传算法主循环
def genetic_algorithm(population_size, chromosome_length, generations, mutation_rate):
    population = initialize_population(population_size, chromosome_length)

    for generation in range(generations):
        # 2. 适应度评估
        fitness_scores = [fitness(individual) for individual in population]
        best_individual = population[fitness_scores.index(max(fitness_scores))]
        print(f"Generation {generation + 1}, Best Fitness: {fitness(best_individual)}")

        # 3. 选择
        selected_population = selection(population)

        # 4. 交叉
        offspring = []
        for _ in range(population_size // 2):
            parent1, parent2 = random.sample(selected_population, 2)
            child1, child2 = crossover(parent1, parent2)
            offspring.extend([child1, child2])

        # 5. 变异
        offspring = [mutation(individual, mutation_rate) for individual in offspring]

        # 6. 替换
        population = replacement(population, offspring)

    return best_individual

# 运行遗传算法
best_solution = genetic_algorithm(population_size=50, chromosome_length=10, generations=50, mutation_rate=0.1)
print("Best Solution:", best_solution)
print("Best Fitness:", fitness(best_solution))

这个示例是一个简单的二进制优化问题,目标是找到染色体中1的数量最多的个体。在实际应用中,你需要根据具体问题调整适应度函数、交叉、变异等操作。

4 遗传算法解决TSP(旅行商问题) 

        考虑一个实际的遗传算法问题:TSP(旅行商问题)。在TSP中,旅行商要访问一组城市,并找到一条最短路径,使得每个城市都被访问一次,然后返回起始城市。 

下面是一个简单的Python实例,演示如何使用遗传算法解决TSP:

import numpy as np
import random

# 生成城市坐标
def generate_cities(num_cities):
    return np.random.rand(num_cities, 2)

# 计算路径长度
def calculate_distance(path, cities):
    distance = 0
    for i in range(len(path) - 1):
        distance += np.linalg.norm(cities[path[i]] - cities[path[i + 1]])
    distance += np.linalg.norm(cities[path[-1]] - cities[path[0]])  # 回到起始城市
    return distance

# 初始化种群
def initialize_population(population_size, num_cities):
    return [random.sample(range(num_cities), num_cities) for _ in range(population_size)]

# 选择操作
def selection(population, cities):
    fitness_scores = [1 / calculate_distance(individual, cities) for individual in population]
    total_fitness = sum(fitness_scores)
    probabilities = [score / total_fitness for score in fitness_scores]
    selected_indices = random.choices(range(len(population)), weights=probabilities, k=len(population))
    return [population[i] for i in selected_indices]

# 交叉操作
def crossover(parent1, parent2):
    crossover_point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:crossover_point] + [city for city in parent2 if city not in parent1[:crossover_point]]
    child2 = parent2[:crossover_point] + [city for city in parent1 if city not in parent2[:crossover_point]]
    return child1, child2

# 变异操作
def mutation(individual):
    index1, index2 = random.sample(range(len(individual)), 2)
    individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 遗传算法主循环
def genetic_algorithm(num_cities, population_size, generations):
    cities = generate_cities(num_cities)
    population = initialize_population(population_size, num_cities)

    for generation in range(generations):
        # 选择
        selected_population = selection(population, cities)

        # 交叉
        offspring = []
        for _ in range(population_size // 2):
            parent1, parent2 = random.sample(selected_population, 2)
            child1, child2 = crossover(parent1, parent2)
            offspring.extend([child1, child2])

        # 变异
        offspring = [mutation(individual) for individual in offspring]

        # 替换
        population = offspring

        # 打印每一代的最优解
        best_individual = min(population, key=lambda x: calculate_distance(x, cities))
        print(f"Generation {generation + 1}, Best Distance: {calculate_distance(best_individual, cities)}")

    # 返回最终的最优解
    best_individual = min(population, key=lambda x: calculate_distance(x, cities))
    return best_individual, calculate_distance(best_individual, cities)

# 运行遗传算法
num_cities = 10
population_size = 50
generations = 100
best_solution, best_distance = genetic_algorithm(num_cities, population_size, generations)

print("\nBest Solution:")
print(best_solution)
print("Best Distance:", best_distance)

        这个例子中,我们随机生成了一组城市,并使用遗传算法寻找最短路径。在每一代,通过选择、交叉、变异和替换操作,逐步优化种群。最终,我们输出找到的最优路径和对应的路径长度。这个例子可以帮助你理解如何将遗传算法应用于解决实际的优化问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150306.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

四川芸鹰蓬飞商务信息咨询有限公司是可靠的选择

随着电商行业的快速发展&#xff0c;越来越多的消费者选择通过线上平台购物。在这个大背景下&#xff0c;四川芸鹰蓬飞商务信息咨询有限公司以其独特的抖音电商服务&#xff0c;为广大消费者带来了更加便捷、安全的购物体验。 一、服务的优势 专业团队&#xff1a;公司拥有一支…

蓝桥杯算法双周赛心得——深秋的苹果(二分+贪心分组前缀和)

大家好&#xff0c;我是晴天学长&#xff0c;二分的check函数&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .深秋的苹果 问题描述 当深秋的苹果树丰收时&#xff0c;村庄的居民们兴致勃勃地采摘着红彤…

QGIS之二十一栅格数据重投影坐标系

效果 步骤 1、准备数据 2、栅格重投影 Qgis工具箱中搜索“投影” 指定重投影坐标系&#xff0c;例如EPSG&#xff1a;3857 运行 3、结果 查看属性

栈:括号匹配问题!

目录 题目&#xff1a; 思路分析&#xff1a; 解题思路&#xff1a; 一、配对&#xff1a; 二、数量问题&#xff1a; 三、细节问题&#xff1a; 完整代码&#xff1a; 手撕栈&#xff1a; 题目&#xff1a; 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&…

【python】Django——连接mysql数据库

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ 【Django专栏】 Django——django简介、django安装、创建项目、快速上手 Django——templates模板、静态文件、django模板语法、请求和响应 Django——连接mysql数据库 Django——连接mysql数据库 连接MySQL数据库…

Git本地项目提交到Gitee的操作流程

一、Gitee创建一个仓库 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 第四步&#xff1a;复制该仓库地址&#xff08;https://gitee.com/yassels/test_1115.git&#xff09;&#xff0c;留待后续使用 二、操作本地文件上传到Gitee 第一步&#xff1a; 第二步…

Dreamweaver替代方案!免费开源网页开发工具推荐,超实用不容错过!

虽然Adobedreamweaver非常好用&#xff0c;但它并不是唯一一个可以设计、开发和发布精彩网站的Web开发集成环境。在我们的开源世界里&#xff0c;有许多优秀的Web开发工具&#xff0c;可以完全取代dreamweaver的各种功能&#xff0c;更重要的是&#xff0c;它们是免费的。如果您…

找不同游戏-第15届蓝桥第二次STEMA测评Scratch真题精选

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥杯真题&#xff0c;这是Scratch蓝桥杯真题解析第157讲。 第15届蓝桥杯第2次STEMA测评已于2023年10月29日落下帷幕&#xff0c;编程题一共有6题&#xff0c;分别如下&…

JavaWeb-HTML

​ 一、什么是HTML HTML是hypertext markup language&#xff08;超文本标记语言&#xff09;的缩写。HTML文件本质上是文本文件&#xff0c;普通的文本文件只能显示字符&#xff0c;而HTML文件可以在浏览器上显示更丰富的信息&#xff08;如图片等&#xff09;。 超文本&am…

Go语言fyne开发桌面应用程序-环境安装

环境安装 参考https://developer.fyne.io/started/#prerequisites网站 之前的文章介绍了如何安装GO语言这里不在叙述 msys2 首先安装msys2&#xff0c;https://www.msys2.org/ 开始菜单打开MSYS2 执行 $ pacman -Syu$ pacman -S git mingw-w64-x86_64-toolchain注意&#…

企业大文件传输的四大误区:你还在用传统的FTP和网盘吗?

在当前数字化时代&#xff0c;数据已经成为企业的核心资产&#xff0c;而文件传输则是数据流动的重要方式。企业需要高效、安全、稳定地传输各种类型和规模的文件&#xff0c;无论是内部协作还是外部交付。然而&#xff0c;很多企业在文件传输方面存在一些误区&#xff0c;导致…

Python交易-通过Financial Modeling Prep (FMP)选择行业

介绍 在您的交易旅程中,无论您是在寻找理想的股票、板块还是指标,做出明智的决策对于您的成功至关重要。然而,收集和分析所需的大量数据可能相当艰巨。财务建模准备 (FMP) API的

jenkins+centos7上传发布net6+gitlab

工作中实践了一下jenkins的操作&#xff0c;所以记录一下这次经验 首先安装好jenkins并注册自己的jenkins账号 因为我们的项目代码管理使用的是gitlab&#xff0c;在开始之前先在jenkins上安装gitlab的插件&#xff0c;安装之后应该是要重启jenkins的服务&#xff0c;后续jen…

无线终端掉线问题专题

一、终端连接过程 1、通过beacon或者probe帧发现设备 2、accoc和auth过程 3、EAP过程 4、DHCP过程 5、portal过程 6、终端检测wlan是否可以上网 7、正常接入网络 二、终端无法上网 终端无法上网则说明终端在连接过程中某一个环节除了问题 1、发现AP过程&#xff0c;p…

【论文精读2】R-MVSNet

R-MVSNet【递归多视图立体网络】&#xff0c;论文全名&#xff1a;“Recurrent MVSNet for High-resolution Multi-view Stereo Depth Inference”&#xff0c;CVPR 2019(CCF A) 在MVSNet的基础上做了一些改进&#xff0c;主要解决的问题是代价体正则化&#xff08;Cost Volume…

Mysql执行报错:[Err] 1292 - Truncated incorrect DOUBLE value:***

MySQL执行语句抛出异常&#xff1a; 上面错误提示概是下面几种情况&#xff1a; 数据类型不匹配&#xff1a;在进行数值比较或运算时&#xff0c;数据类型可能不匹配。例如&#xff0c;将一个字符串值与一个 DOUBLE 类型的列进行比较或运算&#xff0c;或者将一个非数字字符串…

Android设计模式--策略模式

每天都要完成一个小目标 一&#xff0c;定义 策略模式定义了一系列的算法&#xff0c;并将每一个算法封装起来&#xff0c;而且使他们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化 什么意思呢&#xff1f;在我们平时的开发中&#xff0c;难免会遇到这种情况&…

【eNSP安装与使用】华为eNSP网络设备模拟器从安装到使用详细步骤(亲测有效,附安装包下载)

目录 写在前面涉及知识一、安装那些事1.1前期安装包准备&#xff08;基于windows10环境测试&#xff09;1.2 安装WinPcap1.3 安装Wireshark1.4 安装VirtualBox1.5 安装eNSP 二、使用那些事2.1 安装问题解决&#xff08;启动设备ar1失败 错误代码41&#xff09;2.2 测试使用 三、…

干货分享---- 金融贷款电销获客的方法、渠道

电话营销的现状是&#xff0c;它过去使用电话资源在常规交易平台上正常工作&#xff0c;但进入时&#xff0c;对方总是挂断电话&#xff0c;甚至被他人标记为骚扰&#xff0c;这使工作变得困难。事实上&#xff0c;电话营销交易量飙升的关键很简单&#xff0c;那就是营销技巧和…

AGI+机器人行业:AGI 赋能人形机器人,具身智能时代有望加速到来

目录 1AGI的关键拼图&#xff1a;起于大模型&#xff0c;终于具身智能 .2 具身智能助力AGI走进现实 3人形机器人是AGI最佳载体&#xff0c;业界研究进展加速 2.2 OpenAI升级迭代GPT&#xff0c;推动机器人“大脑”升级 2.3 Meta与CMU联手打造RoboAgent&#xff0c;用更少的…