精华内容
下载资源
问答
  • 算法优化

    千次阅读 2008-12-22 19:29:00
    赖勇浩:从一道笔试题谈算法优化(上)2008-12-19 来自:villa123 [收藏到我的网摘]因为受到经济危机的影响,我在 bokee.com 的博客可能随时出现无法访问的情况;因此将2005年到2006年间在 bokee.com 撰写的博客...

    赖勇浩:从一道笔试题谈算法优化(上)
    2008-12-19 来自:villa123  [收藏到我的网摘]
    因为受到经济危机的影响,我在 bokee.com 的博客可能随时出现无法访问的情况;因此将2005年到2006年间在 bokee.com 撰写的博客文章全部迁移到 csdn 博客中来,本文正是其中一篇迁移的文章。

     

    声明:本文最初发表于《电脑编程技巧与维护》2006年第5期,版本所有,如蒙转载,敬请连此声明一起转载,否则追究侵权责任。

    从一道笔试题谈算法优化(上)
    作者:赖勇浩(http://blog.csdn.net/lanphaday

    引子
    每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时,网上也开始出现大量笔试面试题;网上流传的题目往往都很精巧,既能让考查基础知识,又在平淡中隐含了广阔的天地供优秀学生驰骋。

    这两天在网上淘到一道笔试题目(注1),虽然真假未知,但的确是道好题,题目如下:

    从10亿个浮点数中找出最大的1万个。

    这是一道似易实难的题目,一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨,在常见计算机平台(如Win32)上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法,比如每次处理100万个数,然后再综合起来。不过这不是本文要讨论的主旨,所以本文把上题的10亿改为1亿,把浮点数改为整数,这样可以直接地完成这个问题,有利于清晰地讨论相关算法的优化(注2)。

    不假思索
    拿到这道题,马上就会想到的方法是建立一个数组把1亿个数装起来,然后用for循环遍历这个数组,找出最大的1万个数来。原因很简单,因为如果要找出最大的那个数,就是这样解决的;而找最大的1万个数,只是重复1万遍而已。

    template< class T >

    void solution_1( T BigArr[], T ResArr[] )

    {

    for( int i = 0; i < RES_ARR_SIZE; ++i )

    {

    int idx = i;

    for( int j = i+1; j < BIG_ARR_SIZE; ++j )

    {

    if( BigArr[j] > BigArr[idx] )

    idx = j;

    }

    ResArr[i] = BigArr[idx];

    std::swap( BigArr[idx], BigArr[i] );

    }

    }

    设BIG_ARR_SIZE = 1亿,RES_ARR_SIZE = 1万,运行以上算法已经超过40分钟(注3),远远超过我们的可接受范围。

    稍作思考
    从上面的代码可以看出跟SelectSort算法的核心代码是一样的。因为SelectSort是一个O(n^2)的算法(solution_1的时间复杂度为O(n*m),因为solution_1没有将整个大数组全部排序),而我们又知道排序算法可以优化到O(nlogn),那们是否可以从这方面入手使用更快的排序算法如MergeSor、QuickSort呢?但这些算法都不具备从大至小选择最大的N个数的功能,因此只有将1亿个数按从大到小用QuickSort排序,然后提取最前面的1万个。

    template< class T, class I >

    void solution_2( T BigArr[], T ResArr[] )

    {

    std::sort( BigArr, BigArr + BIG_ARR_SIZE, std::greater_equal() );

    memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );

    }

    因为STL里的sort算法使用的是QuickSort,在这里直接拿来用了,是因为不想写一个写一个众人皆知的QuickSort代码来占篇幅(而且STL的sort高度优化、速度快)。

    对solution_2进行测试,运行时间是32秒,约为solution_1的1.5%的时间,已经取得了几何数量级的进展。

    深入思考
    压抑住兴奋回头再仔细看看solution_2,你将发现一个大问题,那就是在solution_2里所有的元素都排序了!而事实上只需找出最大的1万个即可,我们不是做了很多无用功吗?应该怎么样来消除这些无用功?

    如果你一时没有头绪,那就让我慢慢引导你。首先,发掘一个事实:如果这个大数组本身已经按从大到小有序,那么数组的前1万个元素就是结果;然后,可以假设这个大数组已经从大到小有序,并将前1万个元素放到结果数组;再次,事实上这结果数组里放的未必是最大的一万个,因此需要将前1万个数字后续的元素跟结果数组的最小的元素比较,如果所有后续的元素都比结果数组的最小元素还小,那结果数组就是想要的结果,如果某一后续的元素比结果数组的最小元素大,那就用它替换结果数组里最小的数字;最后,遍历完大数组,得到的结果数组就是想要的结果了。

    template< class T >

    void solution_3( T BigArr[], T ResArr[] )

    {

    //取最前面的一万个

    memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );

    //标记是否发生过交换

    bool bExchanged = true;

    //遍历后续的元素

    for( int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )

    {

    int idx;

    //如果上一轮发生过交换

    if( bExchanged )

    {

    //找出ResArr中最小的元素

    int j;

    for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j )

    {

    if( ResArr[idx] > ResArr[j] )

    idx = j;

    }

    }

    //这个后续元素比ResArr中最小的元素大,则替换。

    if( BigArr[i] > ResArr[idx] )

    {

    bExchanged = true;

    ResArr[idx] = BigArr[i];

    }

    else

    bExchanged = false;

    }

    }

    上面的代码使用了一个布尔变量bExchanged标记是否发生过交换,这是一个前文没有谈到的优化手段——用以标记元素交换的状态,可以大大减少查找ResArr中最小元素的次数。也对solution_3进行测试一下,结果用时2.0秒左右(不使用bExchanged则高达32分钟),远小于solution_2的用时。

    深思熟虑
    在进入下一步优化之前,分析一下solution_3的成功之处。第一、solution_3的算法只遍历大数组一次,即它是一个O(n)的算法,而solution_1是O(n*m)的算法,solution_2是O(nlogn)的算法,可见它在本质上有着天然的优越性;第二、在solution_3中引入了bExchanged这一标志变量,从测试数据可见引入bExchanged减少了约99.99%的时间,这是一个非常大的成功。

    上面这段话绝非仅仅说明了solution_3的优点,更重要的是把solution_3的主要矛盾摆上了桌面——为什么一个O(n)的算法效率会跟O(n*m)的算法差不多(不使用bExchanged)?为什么使用了bExchanged能够减少99.99%的时间?带着这两个问题再次审视solution_3的代码,发现bExchanged的引入实际上减少了如下代码段的执行次数:

    for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j )

    {

    if( ResArr[idx] > ResArr[j] )

    idx = j;

    }

    上面的代码段即是查找ResArr中最小元素的算法,分析它可知这是一个O(n)的算法,到此时就水落石出了!原来虽然solution_3是一个O(n)的算法,但因为内部使用的查找最小元素的算法也是O(n)的算法,所以就退化为O(n*m)的算法了。难怪不使用bExchanged使用的时间跟solution_1差不多;这也从反面证明了solution_3被上面的这一代码段导致性能退化。使用了bExchanged之后因为减少了很多查找最小元素的代码段执行,所以能够节省99.99%的时间!

    至此可知元凶就是查找最小元素的代码段,但查找最小元素是必不可少的操作,在这个两难的情况下该怎么去优化呢?答案就是保持结果数组(即ResArr)有序,那样的话最小的元素总是最后一个,从而省去查找最小元素的时间,解决上面的问题。但这也引入了一个新的问题:保持数组有序的插入算法的时间复杂度是O(n)的,虽然在这个问题里插入的数次比例较小,但因为基数太大(1亿),这一开销仍然会令本方案得不偿失。

    难道就没有办法了吗?记得小学解应用题时老师教导过我们如果解题没有思路,那就多读几遍题目。再次审题,注意到题目并没有要求找到的最大的1万个数要有序(注4),这意味着可以通过如下算法来解决:

    1) 将BigArr的前1万个元素复制到ResArr并用QuickSort使ResArr有序,并定义变量MinElemIdx保存最小元素的索引,并定义变量ZoneBeginIdx保存可能发生交换的区域的最小索引;

    2) 遍历BigArr其它的元素,如果某一元素比ResArr最小元素小,则将ResArr中MinElemIdx指向的元素替换,如果ZoneBeginIdx == MinElemIdx则扩展ZoneBeginIdx;

    3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中寻找最小元素,并用MinElemIdx保存其它索引;

    4) 重复2)直至遍历完所有BigArr的元素。

    依上算法,写代码如下:

    template< class T, class I >

    void solution_4( T BigArr[], T ResArr[] )

    {

    //取最前面的一万个

    memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );

    //排序

    std::sort( ResArr, ResArr + RES_ARR_SIZE, std::greater_equal() );

    //最小元素索引

    unsigned int MinElemIdx = RES_ARR_SIZE - 1;

    //可能产生交换的区域的最小索引

    unsigned int ZoneBeginIdx = MinElemIdx;

    //遍历后续的元素

    for( unsigned int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i )

    {

    //这个后续元素比ResArr中最小的元素大,则替换。

    if( BigArr[i] > ResArr[MinElemIdx] )

    {

    ResArr[MinElemIdx] = BigArr[i];

    if( MinElemIdx == ZoneBeginIdx )

    --ZoneBeginIdx;

    //查找最小元素

    unsigned int idx = ZoneBeginIdx;

    unsigned int j = idx + 1;

    for( ; j < RES_ARR_SIZE; ++j )

    {

    if( ResArr[idx] > ResArr[j] )

    idx = j;

    }

    MinElemIdx = idx;

    }

    }

    }

    经过测试,同样情况下solution_4用时约1.8秒,较solution_3效率略高,总算不负一番努力。

     

    待续……

    展开全文
  • 剪枝算法(算法优化)

    万次阅读 多人点赞 2015-03-05 10:40:56
    总之,剪枝策略,属于算法优化范畴;通常应用在DFS 和 BFS 搜索算法中;剪枝策略就是寻找过滤条件,提前减少不必要的搜索路径。 二:剪枝算法(算法优化) 1、简介  在搜索算法中优化中,剪枝,就是通过某种判断,...

    一:剪枝策略的寻找的方法

    1)微观方法:从问题本身出发,发现剪枝条件

    2)宏观方法:从整体出发,发现剪枝条件。

    3)注意提高效率,这是关键,最重要的。

    总之,剪枝策略,属于算法优化范畴;通常应用在DFS 和 BFS 搜索算法中;剪枝策略就是寻找过滤条件,提前减少不必要的搜索路径。

    二:剪枝算法(算法优化)

    1、简介

        在搜索算法中优化中,剪枝,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是剪去了搜索树中的某些“枝条”,故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法,即确定哪些枝条应当舍弃,哪些枝条应当保留的方法。

    2、剪枝优化三原则: 正确、准确、高效.原则

         搜索算法,绝大部分需要用到剪枝.然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍. 在设计判断方法的时候,需要遵循一定的原则.

    剪枝的原则

      1) 正确性

      正如上文所述,枝条不是爱剪就能剪的. 如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义. 所以,剪枝的前提是一定要保证不丢失正确的结果.

      2)准确性

      在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的. 可以说,剪枝的准确性,是衡量一个优化算法好坏的标准.

     3)高效性

    设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的. 倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了.

    3、分类

       剪枝算法按照其判断思路可大致分成两类:可行性剪枝及最优性剪枝.

    3.1 可行性剪枝 —— 该方法判断继续搜索能否得出答案,如果不能直接回溯。

    3.2 最优性剪枝

        最优性剪枝,又称为上下界剪枝,是一种重要的搜索剪枝策略。它记录当前得到的最优值,如果当前结点已经无法产生比当前最优解更优的解时,可以提前回溯。

    三:示例分析

    题目来源于poj 3900 The Robbery (类似于背包问题,但是不能够用背包求解)

    1 分析:W,C值很大,数组开不下(所以,不能用背包处理),但是发现N值很小,(1+15)*15/2=120,所以可以考虑dfs+剪枝。

    首先利用贪心的思想我们对箱子进行排序,关键字为性价比(参考了poj里的discuss)。也就是单位重量的价值最高的排第一,搜索的时候枚举顺序注意一定要从满到空,这样才能最快的找到一个可行解然后利用它进行接下来的剪枝。

    剪枝1. 之后所有的钻石价值+目前已经得到的价值<=ans 则剪枝。

    剪枝2. 剩下的重量全部装目前最高性价比的钻石+目前已经得到的价值<=ans 则剪枝(非常重要的剪枝)。

    2 程序代码

    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define MY_MAX(a,b) (a)>(b)?(a):(b)
    const int maxN = 20;
    struct NOTE
    {
        long long weight;
        long long value;
        int num;
    }box[maxN];
    int n;// 个数小于20
    long long m,ans;// m 总重量,ans最优解
    long long sum[maxN];      //保存一个后缀和
    bool cmp(const struct NOTE &a, const struct NOTE &b)
    {//按性价比排序,从大到小排列(注意若有取地址符号,则需有const)
        return a.value*1.0/a.weight > b.value*1.0/b.weight;
    }
    inline bool cut (int pos,long long now_value,long long last_weight)
    {
        if(pos == n+1) return true;//边界返回条件
        if(now_value+sum[pos] < ans) return true;如果后面所有的钻石加起来都<=ans,剪掉
        double best = (box[pos].value*1.0/box[pos].weight);//当前最大的性价比
        if(now_value+(long long)ceil(best*last_weight) < ans) return true;//以这个性价比取剩下的所有重量,如果<=ans,剪掉
        return false;
    }
    void dfs(int pos,long long now_value,long long last_weight) //pos 当前数组的下标位置,now_value 目前的重量和,last_weight当前背包剩余容量
    {
        ans = MY_MAX(ans,now_value);
        if(cut(pos,now_value,last_weight))  return;//剪枝函数
        for(int i=box[pos].num;i>=0;--i)//(暴力搜索)枚举顺序从满到空枚举,这样才能最快找到ans,然后利用ans剪枝
        {
            if(last_weight<box[pos].weight*i)   continue;
            dfs(pos+1,now_value+box[pos].value*i,last_weight-box[pos].weight*i);
        }
    }
    int main()
    {
        int cas;
        long long sumv,sumw;// 价值和重量的和;仅仅用到了一次(特殊情况才用到,能够一次全带走)
        scanf("%d",&cas);
        while(cas--)
        {
            ans=0;
            sumv=sumw=0;
            scanf("%d%lld",&n,&m);
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&box[i].weight);
                sumw+=box[i].weight*i;
            }
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&box[i].value);
                box[i].num=i;
                sumv+=box[i].value*i;
            }
            // 以上是数据的输入,下面才是刚刚开始的
            // 如果sumv开始就比m总重量还小,直接输出
            if(sumw<=m)
            {
                printf("%lld\n",sumv);
                continue;
            }
            sort(box+1,box+1+n,cmp);// 从1开始计数的
            sum[n+1]=0; // 倒着开始的
            for(int i=n;i>=1;i--)
            {
             //计算后缀和
                sum[i]=sum[i+1]+box[i].value*box[i].num;
            }
            dfs(1,0,m);
            printf("%lld\n",ans);
        }
        return 0;
    }




    展开全文
  • Floyd算法优化

    千次阅读 2017-09-06 11:47:52
    Floyd算法优化

    Floyd算法优化


    参考:
    非加权无向图 Floyd-Warshall 算法优化与改进


    经典实现

    void Floyd(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    A[i][j] = min(A[i][j], A[i][k]+A[k][j]);
                }
            }
        }
        return ;
    }

    利用矩阵的对称性

    void Floyd_1(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                int t = A[i][k];
                for(int j = 1; j <= i; j++){
                    A[i][j] = min(A[i][j], t+A[k][j]);
                    A[j][i] = A[i][j];
                }
            }
        }
        return ;
    }

    只使用矩阵的下三角部分

    void Floyd_2(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    for(int j = 1; j <= min(k,i); j++){
                        A[i][j] = min(A[i][j], t+A[k][j]);
                    }
                    for(int j = k+1; j <= i; j++){
                        A[i][j] = min(A[i][j], t+A[j][k]);
                    }
                }
            }
        }
        return ;
    }

    跳过不存在的路径

    void Floyd_3(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    if(t == Inf)  continue;
                    for(int j = 1; j <= min(k,i); j++){
                        A[i][j] = min(A[i][j], t+A[k][j]);
                    }
                    for(int j = k+1; j <= i; j++){
                        A[i][j] = min(A[i][j], t+A[j][k]);
                    }
                }
            }
        }
        return ;
    }

    避免大量调用数学函数

    void Floyd_4(){
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                if(k != i){
                    int t = (k<i) ? A[i][k] : A[k][i];
                    if(t == Inf)  continue;
                    for(int j = 1; j <= ((k<i)?k:i); j++){
                        if(t+A[k][j] < A[i][j])  A[i][j] = t + A[k][j];
                    }
                    for(int j = k+1; j <= i; j++){
                        if(t+A[j][k] < A[i][j])  A[i][j] = t + A[j][k];
                    }
                }
            }
        }
        return ;
    }
    展开全文
  • 遗传优化算法优化LSTM结构-准确率

    千次阅读 多人点赞 2020-11-18 16:18:28
    文章目录神经网络部分遗传算法优化部分结果部分 话不多说,直接上代码 神经网络部分 #!usr/bin/env python # -*- coding:utf-8 _*- """ @author: liujie @software: PyCharm @file: main.py @time: 2020/11/17 20:46...


    话不多说,直接上代码

    神经网络部分

    #!usr/bin/env python
    # -*- coding:utf-8 _*-
    """
    @author: liujie
    @software: PyCharm
    @file: main.py
    @time: 2020/11/17 20:46
    """
    '''
        整体思路:
            1.首先,写一个main.py文件进行神经网络的训练及测试过程
            2.将main.py中需要优化的参数(这里我们优化LSTM层数和全连接层数及每层神经元的个数)统一写到一个列表num中
            3.然后,遗传算法编写GA.py,用需要传入main.py文件的列表num当染色体,需要优化的参数是染色体上的基因
            
        main.py文件中,由于需要将所有优化的参数写到一个列表中,所以需要在文件中定义两个函数,
        分别是创建LSTM函数creat_lstm(inputs,units,return_sequences)
             创建全连接层函数creat_dense(inputs,units)
    '''
    
    import numpy as np
    import tensorflow as tf
    import pandas as pd
    import matplotlib.pylab as plt
    
    from tensorflow import keras
    from tensorflow.keras.layers import LSTM, Dense, Dropout, BatchNormalization, Input
    from tensorflow.keras import optimizers, losses, metrics, models
    
    
    # 定义LSTM函数
    def create_lstm(inputs, units, return_sequences):
        '''
        定义LSTM函数
        :param inputs:输入,如果这一层是第一层LSTM层,则传入layers.Input()的变量名,否则传入的是上一个LSTM层
        :param units: LSTM层的神经元
        :param return_sequences: 如果不是最后一层LSTM,都需要保留所有输出以传入下一LSTM层
        :return:
        '''
        lstm = LSTM(units, return_sequences=return_sequences)(inputs)
        print('LSTM: ', lstm.shape)
        return lstm
    
    
    def create_dense(inputs, units):
        '''
        定义Dense层函数
        :param inputs:输入,如果这一连接层是第一层全连接层,则需传入layers.Flatten()的变量名
        :param units: 全连接层单元数
        :return: 全连接层,BN层,dropout层
        '''
        # dense层
        dense = Dense(units, kernel_regularizer=keras.regularizers.l2(0.001), activation='relu')(inputs)
        print('Dense:', dense.shape)
        # dropout层
        dense_dropout = Dropout(rate=0.2)(dense)
    
        dense_batch = BatchNormalization()(dense_dropout)
        return dense, dense_dropout, dense_batch
    
    
    def load():
        '''
        数据集加载
        :return:
        '''
        (x_train, y_train), (x_test, y_test) = keras.datasets.mnist.load_data()
        # 数据集归一化
        x_train, x_test = x_train / 255.0, x_test / 255.0
        return x_train, y_train, x_test, y_test
    
    
    def classify(x_train, y_train, x_test, y_test, num):
        '''
        利用num及上面定义的层,构建模型
        :param x_train:
        :param y_train:
        :param x_test:
        :param y_test:
        :param num: 需要优化的参数(LSTM和全连接层层数以及每层神经元的个数),同时,也是遗传算法中的染色体
        :return:
        '''
        # 设置LSTM层参数
        lstm_num_layers = num[0]
        lstm_units = num[2:2 + lstm_num_layers]
        lstm_name = list(np.zeros((lstm_num_layers,)))
    
        # 设置LSTM_Dense层的参数
        lstm_dense_num_layers = num[1]
        lstm_dense_units = num[2 + lstm_num_layers: 2 + lstm_num_layers + lstm_dense_num_layers]
        lstm_dense_name = list(np.zeros((lstm_dense_num_layers,)))
        lstm_dense_dropout_name = list(np.zeros((lstm_dense_num_layers,)))
        lstm_dense_batch_name = list(np.zeros((lstm_dense_num_layers,)))
    
        inputs_lstm = Input(shape=(x_train.shape[1], x_train.shape[2]))
    
        for i in range(lstm_num_layers):
            if i == 0:
                inputs = inputs_lstm
            else:
                inputs = lstm_name[i - 1]
            if i == lstm_num_layers - 1:
                return_sequences = False
            else:
                return_sequences = True
    
            lstm_name[i] = create_lstm(inputs, lstm_units[i], return_sequences=return_sequences)
    
        for i in range(lstm_dense_num_layers):
            if i == 0:
                inputs = lstm_name[lstm_num_layers - 1]
            else:
                inputs = lstm_dense_name[i - 1]
    
            lstm_dense_name[i], lstm_dense_dropout_name[i], lstm_dense_batch_name[i] = create_dense(inputs,
                                                                                                    units=lstm_dense_units[
                                                                                                        i])
    
        outputs_lstm = Dense(10, activation='softmax')(lstm_dense_batch_name[lstm_dense_num_layers - 1])
    
        # 构建模型
        LSTM_model = keras.Model(inputs=inputs_lstm, outputs=outputs_lstm)
        # 编译模型
        LSTM_model.compile(optimizer=optimizers.Adam(),
                           loss='sparse_categorical_crossentropy',
                           metrics=['accuracy'])
    
        history = LSTM_model.fit(x_train, y_train,
                                 batch_size=32, epochs=1, validation_split=0.1, verbose=1)
        # 验证模型
        results = LSTM_model.evaluate(x_test, y_test, verbose=0)
        return results[1]  # 返回测试集的准确率
    
    

    遗传算法优化部分

    #!usr/bin/env python
    # -*- coding:utf-8 _*-
    """
    @author: liujie
    @software: PyCharm
    @file: GA.py
    @time: 2020/11/17 22:28
    """
    '''
        在优化神经网络上,用常规的遗传算法不易实现
        原因如下:
            1.传统的遗传算法中每条染色体的长度相同,但是优化LSTM网络时染色体的长度会因为层数的不同而不同
              比如:a染色体有一层LSTM层和一层全连接层,则这个染色体上共有6个基因(两个代表层数,两个代表神经元个数)
                   b染色体有二层LSTM层和二层全连接层,则这个染色体上共有6个基因(两个代表层数,四个代表每层的神经元个数)
                   
            2.在传统的遗传算法中,染色体上的基因的取值范围是相同的,但是在优化LSTM网络时,需要让表示层数的基因在一个范围内,
              表示神经元个数的基因在另一个范围内,比如层数范围是一到三层,神经元个数是32到256个之间
            3.由于染色体长度不同,交叉函数、变异函数均需要做出修改
            
        解决办法:
            1.将每条染色体设置为相同的长度
              (本题来说,因为LSTM层与全连接层层数最多三层,加上最前面两个表示层数的基因,故每条染色体上有3+3+2 = 8个基因),
              达不到长度要求的后面补零
            2.先设置前面两个基因,令其范围分别在一到三之间,然后根据这两个基因确定后面关于每层神经元个数的基因
            3.对于交叉函数的修改,首先确定取出的两条染色体(设为a染色体和b染色体)上需要交换的位置,然后遍历两条染色体在这些位置的
              基因,如果任一染色体上此位置上的基因为0或要交换的基因是关于层数的,则取消此位置的交换
            4.对于变异函数的修改,只有关于神经元个数的基因变异,关于层数的基因不变异
    '''
    
    import numpy as np
    import main as project
    import os
    os.environ['TF_CPP_MIN_LOG_LEVEL'] = '2'
    
    # 设置参数
    DNA_size = 2
    DNA_size_max = 8    # 每条染色体的长度
    POP_size = 20       # 种群数量
    CROSS_RATE = 0.5    # 交叉率
    MUTATION_RATE = 0.01# 变异率
    N_GENERATIONS = 40  # 迭代次数
    
    x_train,y_train,x_test,y_test = project.load()
    
    # 适应度
    def get_fitness(x):
        return project.classify(x_train,y_train,x_test,y_test,num=x)
    
    # 生成新的种群
    def select(pop,fitness):
        idx = np.random.choice(np.arange(POP_size),size=POP_size,replace=True,p=fitness/fitness.sum())
        return pop[idx]
    
    # 交叉函数
    def crossover(parent,pop):
        if np.random.rand() < CROSS_RATE:
            i_ = np.random.randint(0,POP_size,size=1)   # 染色体的序号
            cross_points = np.random.randint(0,2,size=DNA_size_max).astype(np.bool)     # 用True、False表示是否置换
    
            # 对此位置上基因为0或是要交换的基因是关于层数的,则取消置换
            for i,point in enumerate(cross_points):
                if point == True and pop[i_,i] * parent[i] == 0:
                    cross_points[i] = False
                # 修改关于层数的
                if point == True and i < 2:
                    cross_points[i] = False
            # 将第i_条染色体上对应位置的基因置换到parent染色体上
            parent[cross_points] = pop[i_,cross_points]
        return parent
    
    
    # 定义变异函数
    def mutate(child):
        for point in range(DNA_size_max):
            if np.random.rand() < MUTATION_RATE:
                if point >= 3:
                    if child[point] != 0:
                        child[point] = np.random.randint(32,257)
        return child
    
    # 层数
    pop_layers = np.zeros((POP_size,DNA_size),np.int32)
    pop_layers[:,0] = np.random.randint(1,4,size=(POP_size,))
    pop_layers[:,1] = np.random.randint(1,4,size=(POP_size,))
    
    # 种群
    pop = np.zeros((POP_size,DNA_size_max))
    # 神经元个数
    for i in range(POP_size):
        pop_neurons = np.random.randint(32,257,size=(pop_layers[i].sum(),))
        pop_stack = np.hstack((pop_layers[i],pop_neurons))
        for j,gene in enumerate(pop_stack):
            pop[i][j] = gene
    
    # 迭代次数
    for each_generation in range(N_GENERATIONS):
        # 适应度
        fitness = np.zeros([POP_size,])
        # 第i个染色体
        for i in range(POP_size):
            pop_list = list(pop[i])
            # 第i个染色体上的基因
            # 将0去掉并变整数
            for j,each in enumerate(pop_list):
                if each == 0.0:
                    index = j
                    pop_list = pop_list[:j]
            for k,each in enumerate(pop_list):
                each_int = int(each)
                pop_list[k] = each_int
    
            fitness[i] = get_fitness(pop_list)
            print('第%d代第%d个染色体的适应度为%f'%(each_generation+1,i+1,fitness[i]))
            print('此染色体为:',pop_list)
        print('Generation:',each_generation+1,'Most fitted DNA:',pop[np.argmax(fitness),:],'适应度为:',fitness[np.argmax(fitness)])
    
        # 生成新的种群
        pop = select(pop,fitness)
    
        # 新的种群
        pop_copy = pop.copy()
    
        for i,parent in enumerate(pop):
            child = crossover(parent,pop_copy)
            child = mutate(child)
            pop[i] = child
    

    结果部分

    代码能跑通,自己试一下
    

    如果对您有帮助,麻烦点赞关注,这真的对我很重要!!!如果需要互关,请评论留言!
    在这里插入图片描述


    展开全文
  • 排队算法优化

    千次阅读 2018-07-03 21:47:41
    排队算法优化一、起因 按照订单简单的FIFO排队,做完一桌菜再做下一桌菜,这样会导致大量的等待时间,可会体验会不太好,因此提出以下算法模型。二、若干模型以及算法细节假定我们已经清楚各个菜品制作所需要的时间...
  • 目标检测算法优化技巧

    千次阅读 多人点赞 2019-02-28 08:52:07
    论文:Bag of Freebies for Training Object ...这篇论文介绍目标检测算法的一些优化技巧,目前已经在GluonCV中实现了,整体看下来和之前的那篇图像分类算法优化技巧的论文(Bag of Tricks for Image Classificat...
  • 遗传算法/粒子群算法优化支持向量机分类的代码结果对比 简介 数据集源自意大利葡萄酒种类的数据,支持向量机为libsvm。采用SVM、遗传算法优化SVM、粒子群算法优化SVM优化c、g参数,进行分类识别的结果对比。 结果 ...
  • GA-BP模型建立3.1 模型与数据介绍3.2 GA与BP参数设置3.3 遗传算法优化BP的设计4. 测试结果 1. BP神经网络预测原理简介 BP 神经网络是一种多层前馈神经网络,常用的为输入层-单隐含层-输出层的三层结构,如下图所示...
  • 【算法】AES算法优化

    千次阅读 2013-02-05 13:42:43
    算法优化主要就是在矩阵相乘中,优化的方式也很简单,就是空间换时间。 AES算法的矩阵是有特点的,矩阵如下: 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 每一竖行都是02 01 01 03 ...
  • 遗传算法优化BP神经网络分为BP神经网络结构确定、遗传算法优化和 BP神经网络预测3个部分。其中,BP神经网络结构确定部分根据拟合函数输入输出参数个数确定 BP神经网络结构,这样就可以确定遗传算法的优化参数个数,...
  • KNN算法优化

    千次阅读 2018-06-08 21:39:54
    优化(1)   由上面的例子可见:该算法在分类时有个重要的不足是,当样本不平衡时,即:一个类的样本容量很大,而其他类样本数量很小时,很有可能导致当输入一个未知样本时,该样本的K个邻居中大数量类的样本占多...
  • 粒子群算法优化BP神经网络

    万次阅读 多人点赞 2017-06-09 09:58:12
    刚学粒子群算法,然后用粒子群算法优化神经网络的隐藏节点数,代码写的不是太好,如果代码有问题,请大家多多指教。第一次写博客,多多包涵。 本文的粒子群算法用的是标准粒子群算法,权重更新采用线性递减策略。
  • 基于麻雀搜索算法优化的SVM数据分类预测 - 附代码 文章目录基于麻雀搜索算法优化的SVM数据分类预测 - 附代码1.数据集2.SVM模型建立3.基于麻雀算法优化的SVM4.测试结果5.参考文献:6.Matlab代码 摘要:为了提高SVM...
  • 遗传算法优化BP神经网络拟合非线性函数

    万次阅读 多人点赞 2018-08-09 19:45:58
    本文主要是讲遗传算法用于优化BP算法,BP算法在拟合非线性函数时,虽然可以收敛,但是有可能收敛到局部最小点,这是源于它的搜索是串行搜索,而遗传算法的并行性,能够使其更容易收敛到全局最小点。在训练神经网络时...
  •  以下才是真正意义上的优化,有时候我们在面试的时候遇到招 FPGA算法优化工程师,糊弄起来,是,我们用FPGA对算法实现了优化加速,其实不是真正意义上的算法优化。但是如果你面试的时候说了实话,说自己不会做算法...
  • 嵌入式图像处理算法优化

    千次阅读 2017-08-26 16:04:11
    嵌入式图像处理算法优化指南,适用于任何基于ARM或PC平台的视觉应用程序开发 转载2015-08-05 15:09:15 标签:目标识别与跟踪视觉定位与目标识别视觉算法研究与验证视频图像处理开发板it 第一章 绪论 ...
  • 遗传算法优化BP神经网络

    万次阅读 多人点赞 2017-06-02 21:28:14
    遗传算法GA—模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。(具有“生存+检测”的迭代过程的搜索算法)基于自然界“优胜劣汰,适者生存”的生物进化原理引入优化参数形成的编码串联群体中,...
  • 基于麻雀搜索算法优化的SVM回归预测 文章目录基于麻雀搜索算法优化的SVM回归预测1.数据集3.模型处理4.基于麻雀搜索的SVM回归预测5.测试结果:6.参考文献7.matlab代码 摘要:利用麻雀搜索算法对SVM回归预测进行优化。...
  • 冒泡排序算法优化

    万次阅读 多人点赞 2018-07-26 10:51:54
    ————— 当天上午 ————— ...大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。...而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡...
  • 算法优化策略

    千次阅读 2017-06-18 21:45:31
    5、问题的算法特征 (1)贪心策略(货物储运问题) 相同层序定理:存在货物储运问题的最优合并树,其各原始结点在最优合并树种所处的层序与相应的原始结点在相容合并树中所处的层序相同。 算法三部曲: 组合、...
  • Matlab遗传算法优化的BP神经网络(两个隐含层)

    千次阅读 多人点赞 2019-05-05 19:55:16
    看了王小川的《MATLAB神经网络43个案例分析》,第三章的遗传算法优化BP神经网络,讲了只有一个隐含层的神经网络如何使用遗传算法优化,这个代码网络上现在都有,我刚开始用这个代码跑了一下自己的样本,结果效果不好...
  • PID算法优化(以平衡小车代码为例)

    千次阅读 多人点赞 2019-08-04 15:59:46
    PID控制 这篇文章是PID控制的进阶说明,如果没有看过PID控制(上)的读者,请先看看PID控制(上),以便更容易看懂这篇文章。关注微信公众号“电子搬砖师”即可阅读PID控制(上)。...先讲PID算法优化,奉上...
  • 一文搞懂RMSProp优化算法优化

    千次阅读 2020-03-26 16:01:21
    首发于机器学习算法与自然语言处理关注专栏写文章【优化算法】一文搞懂RMSProp优化算法忆臻​哈尔滨工业大学 计算机科学与技术博士在读73 人赞同了该文章在前面我们讲了AdaGrad算法,见下:忆臻:Deep Learning 最...
  • 一个简单遍历的算法优化

    千次阅读 2018-10-24 18:49:45
    一个简单遍历的算法优化 前几天一个学弟问了我一个C语言的循环遍历的题,其中,题目是这样的: 一个小于10万的正整数,它加上100后是一个完全平方数(即一个数的平方),再加上168又是一个完全平方数,请问该数是...
  • 本微信图文详细介绍了遗传算法优化BP神经网络初始权值阈值的过程,并通过实例说明该优化能够提升BP神经网络的预测精确程度。
  • 温馨小提示:本文章主要提炼了遗传算法(GA)、粒子群算法(PSO)和模拟退火算法(SA)的精髓,故更适合具有一定基础的童鞋加深理解。...(2)确定需要优化的参数 1.1.2 遗传算法的寻优过程 (1)根据之前确定的优
  • 利用遗传算法优化GANs

    千次阅读 2020-12-11 09:16:39
    GANs是在训练阶段最需要计算的密集型模型之一,...在本片文章中,我们尝试使用遗传算法来对训练GANs进行优化,我们的训练模型是生成手写数字。 什么是遗传算法? 遗传算法是一种学习算法,它利用交叉两个好的神经网
  • 基于麻雀搜索算法优化的Elman神经网络数据预测 - 附代码 文章目录基于麻雀搜索算法优化的Elman神经网络数据预测 - 附代码1.Elman 神经网络结构2.Elman 神经用络学习过程3.电力负荷预测概述3.1 模型建立4.基于麻雀...
  • 我想用matlab遗传算法优化simulink中的参数,用simulink的输出作为适值函数,把待优化的参数作为染色体,从而在matlab中实现遗传算法,但是不知道应该怎么把simulink和matlab联系起来,希望大家能帮我解决这个问题。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 895,939
精华内容 358,375
关键字:

算法优化