演化计算(Evolutionary Computation, EC)是自然计算的一个重要分支,它是根据达尔文“优胜劣汰,适者生存”的思想去模仿自然界生物的演化过程。通过对演化过程的抽象及人工编程实现,构造出具有自然演化特征,同时又具有自组织、自适应和自学习的一个通用的求解问题的方法。自组织、自适应和自学习可以概括地称为智能性,这种具有智能性的方法能够解决传统算法难于解决的各种复杂问题,在任务优化、机器学习、工程控制、硬件设计、经济优化等领域均取得了很好的应用。遗传程序设计是演化计算的一个重要分支,是一种自动程序设计方法学。用遗传程序设计进行自动程序设计的目标是计算机自动演化出一个求解问题的计算程序来求解问题。遗传程序设计方法(Genetic Programming, GP)、基因表达式程序设计(Gene Expression Programming, GEP)和多表达式程序设计(Multi Expression Programming, MEP)都属于遗传程序设计方法。GEP和MEP都采用定长的线性基因编码的染色体来表示演化个体,这种定长的染色体采用有效的解码机制把染色体的基因型转化为表现型,从而跨越了表现型的障碍。这种染色体的定长性确定了解空间,线性基因表达的特性则使得所有的遗传操作集中在染色体的基因型中,这使得GEP和MEP同时具有遗传程序设计和遗传算法的优良特性。本文系统地研究了基于线性基因编码的程序设计方法及其若干应用,主要内容及创新点归纳如下：1.阐述了演化计算的基本概念、分支及其特点,并从遗传算法、演化策略、演化规划、GP、GEP、MEP和群体智能等方面论述了演化计算的应用领域及理论研究范畴。提出了用程序设计的网络来表示并记录GEP算法的运行过程和运行信息。借助于复杂网络的分析方法,揭示了程序设计网络具有小世界和无尺度的特性,是一个典型的复杂网络。这种复杂网络特性是程序设计算法“自然”和“本质”的特性；2.提出了基因有效长度的概念,借助基因有效长度提出了基因阅读运算器的染色体适应值的计算方法(Gene Read & Compute Machine, GRCM)。GRCM改变了通过层次化构造树或堆栈技术的适应值计算方法。研究表明GRCM方法构造简单且极具通用性,可在基于线性基因编码的程序设计算法中得到广泛应用。在性能的评估中考虑染色体长度、种群大小、数据集大小以及运算代数四个影响因素,结果表明了GRCM方法的优越性能。提出了演化元程序设计方法(Evolutionary Meta Programming, EMP),构造了三种元机制：Static-Meta、Dynamic-Meta和EDA-Meta,元机制的使用增加了算法的智能性,有效地提高了程序设计方法的运行效率；3.研究了GEP中基因缺乏复用性的特点,提出了基于重叠复用的程序设计方法(Overlap Reuse Programming, ORP)。对于相同的基因型,采用重叠复用技术的染色体(Overlap Reuse Chromosome, ORC)与采用传统的GEP染色体相比具有更为复杂的表现型。分析了MEP方法中基因复用的特性,并结合GEP、ORP和MEP的共同特点,创造性地提出了图分析方法和图表示方法。这种图分析和图表示法不仅是分析算法效率的一个有效媒介,而且具有很高的通用性。图表示是染色体继基因型表示、表现型(树型表示)后的一种新的表示方法,是遗传程序设计方法的共性理论的发展,是演化计算理论的拓展。在图分析方法中通过图表示在四个角度来分析各种程序设计算法的效率(解空间大小、图表示的节点距离、染色体的内在并行性和节点的演化压力)；4.演化算法面临的挑战性问题中一个重要问题就是算法的统一框架。结合GEP、ORP和MEP的共性特点,提出了统一的表达式程序设计方法(United Expression Programming, UEP), UEP在染色体的表示、染色体适应值的计算和适应值的选取上形成统一。研究发现GEP、ORP和MEP可看作是UEP的特例；5.演化算法面临的挑战性问题中另一个重要问题是算法的组合特性,自组织、自适应和自学习是这种组合特性的具体体现。现今算法在实现这些特性的同时大多加入了过多的构造过程和控制因素,这使得算法的自组织、自适应和自学习的特性不能充分体现。本文创造性地提出了算子自动构建的演化算法(Automatic Operator Generated Evolutionary Algorithm, AOGEA),把普通的遗传算法与UEP方法结合后求解函数优化问题,在本质上、微观上实现了算法自组织、自适应和自学习的目标。与经典遗传算法(Simple Genetic Algorithm, SGA)、粒子群优化(Particle Swarm Optimization, PSO)、微分演化(Differential Evolution, DE)和多父体杂交(Multi Crossover, MC)算法相比,AOGEA算法具有更高的运行效率；6.软件测试方法是软件工程的一个重要的概念,而且软件测试是软件项目实施过程中一个至关重要的步骤,本文采用UEP方法来进行类的测试用例的生成,测试实例初步显示了UEP算法的有效性。