[發明專利]一種應用在生產排程系統的基于訂單結構的遺傳操作算子

無效

• 申請號: 200810035774.2
• 申請日: 2008-04-09
• 公開（公告）號: CN101256648A
• 公開（公告）日: 2008-09-03
• 發明（設計）人: 顧永明;陳杰
• 申請（專利權）人: 永凱軟件技術（上海）有限公司
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06N3/12
• 代理公司: 上海新天專利代理有限公司
• 代理人: 王敏杰

1.一種應用在生產排程系統的基于訂單結構的遺傳操作算子，包括選擇、和/或交叉、和/或變異，其特征在于：

①選擇是通過設置選擇率κ為閾值來實現的：若可行解池中個體數目與種群規模的比值小于κ，則可行解池中全部個體作為父代種群；若可行解池中解的數目與種群規模的比值大于κ，則從可行解池中選擇種群規模的κ倍的個體作為父代種群，并從不可行解池中選擇部分個體補足所需種群規模，即使得不可行解池中選擇的個體數目與之前在可行解池選擇的個體數目之和達到種群規模；此處種群規模為計算前預定義的父代種群的大?。?/p>

②交叉是從父代種群中選取一對代表排程方案的基因串個體，并選擇交叉操作算子進行交叉操作生成一對新的個體，存入子代種群，直至子代個數達到交叉率所規定的足夠數目；

③變異是從父代種群中選取一個代表排程方案的基因串個體，并選擇變異操作算子進行變異操作生成一個新的個體，存入子代種群，直至子代個數達到變異率所規定的足夠數目；

2.根據權利要求1所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述①中的選擇率κ閾值設置的范圍為

3.根據權利要求1所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述①中可行解池中解的數目與種群規模的比值大于κ情況下對可行解池中解的選擇，是通過按解適應度值的高低作為其被選擇到的概率，由輪盤賭方式來實現的。

4.根據權利要求1所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述①中不可行解池中解的選擇，是按解的適應度值由高至低的次序來選擇的。

5.根據權利要求1所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述②中的交叉操作算子，為三種交叉操作算子：a.兩段式交叉操作算子：

一父代基因串分兩段和另一父代基因串進行比較、刪除、替換，生成子代基因串；b.訂單位置不變交叉操作算子：一父代基因串保留同一訂單所涉及工單或工序的基因位，其他基因位由另一父代基因串的非所述訂單所涉及工單或工序的基因位進行補充，生成子代基因串；c.訂單加工順序改變交叉操作算子：一父代基因串中同一訂單所涉及工單或工序的基因位由另一父代基因串的所述訂單所涉及工單或工序的基因位進行替換，生成子代基因串。

6.根據權利要求5所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述的兩段式交叉操作算子包括三種子算子：保留父代基因串前段、或保留父代基因串后段、或保留父代基因串較長段。

7.根據權利要求1所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，其特征在于：

所述③中的變異操作算子包括以下兩種交變異操作算子：a.產品加工順序重排列變異算子：父代基因串交換同一訂單所涉及工單或工序的基因位順序，生成子代基因串；b.在可行范圍內隨機插入變異算子：父代基因串隨機選擇某個點插入到串中的不同隨機位置，而可插入的可行范圍受訂單加工順序的約束，變異點多與等于一個。

8.根據權利要求7所述的應用在生產排程系統的基于訂單結構的遺傳操作算子，進行交叉、變異操作，選擇交叉算子、變異操作時，其特征在于：

當交叉操作算子選擇兩段式交叉算子時，變異操作算子選擇在可行范圍內隨機插入變異算子；當交叉操作算子選擇訂單位置不變交叉操作算子時，變異操作算子選擇在可行范圍內隨機插入變異算子；當交叉操作算子選擇加工順序重排列改變交叉操作算子時，變異操作算子選擇產品加工順序重排列變異算子。