基于物元理論的任意功能樹相似擴展方法

劉曉平， 陸勁挺

（合肥工業大學計算機與信息學院可視化與協同計算研究室，安徽 合肥 230009）

基于物元理論的任意功能樹相似擴展方法

劉曉平， 陸勁挺

（合肥工業大學計算機與信息學院可視化與協同計算研究室，安徽 合肥 230009）

功能模型是概念設計的核心處理對象，功能樹是一種典型的、應用廣泛的功能模型。使用現有相似度計算方法計算任意功能樹的相似度存在困難。因此，基于布爾代數提出了析取范式樹的概念，以及兩種求解析取范式樹的方法，并描述了任意功能樹的物元相似度計算方法。拓展了功能樹相似擴展方法的應用范圍，擴大了設計解空間，增加了獲得創新解的可能性，最后給出實例驗證了方法的有效性。

計算機應用；功能樹；析取范式樹；物元相似度

概念設計是產品設計最具有創造性的階段，決定了產品從設計到生產所有費用的75%[1]，決定了產品的創新性和市場競爭力。功能模型是概念設計的核心處理對象[2]，目前在概念設計中的功能模型種類繁多，其中功能樹是一種典型的、應用極其廣泛的功能模型[3-5]。

功能樹的建立主要依賴領域專家的專業知識水平，然而僅憑借人的思維難以將問題考慮全面，所以專家所建的功能樹往往蘊含的信息不完備，因而，需要計算機輔助進行功能樹的擴展，使設計信息盡可能的完備，避免遺失重要的設計解。

現有相似度計算方法難以直接計算結構復雜的功能樹之間的相似度，因此需要一套通用的、能夠對任意功能樹進行比較的相似度計算方法，而后再進行相似擴展。文獻[6]提出了基于人類相似聯想的相似擴展方法的基本思想。基于這種思想筆者在文獻[7]提出了一種有約束的功能樹對比相似度計算方法，以及對比相似擴展的具體方法。但是任意功能樹的相似度計算方法鮮有提及。

由于功能樹的功能函數是布爾表達式，所以結合布爾代數的規則，提出了析取范式樹的概念，并給出兩種求解析取范式樹的算法，最后描述了任意功能樹的相似度計算方法。拓展了功能樹相似擴展方法的應用范圍，擴大了設計解空間，增加了獲得創新解的可能性。

1 背 景

產品概念設計中，功能樹的建立需要先確定總功能，而后采用自頂向下的方法分解總功能，再將其子功能作為總功能進行分解，直到分解得到的子功能為不能再分的基本功能。總功能節點和子功能節點統稱為功能節點，其關系可通過“與”、“或”、“非”3種門節點進行表示，而不可再分的葉子節點為基本功能節點，否則為可擴展功能節點。

定義1 基本功能變量 假設設計需求S最終可分解為n個基本功能，則定義基本功能變量xi為一個布爾變量，其中，

對設計需求的求解，本質上即是對功能樹頂功能實現方案的求解，頂功能變量的值是由基本功能變量決定的。

定義 2 功能函數 對于 n維向量X = (x1,x2,…, xn)，其中任一分量xi為基本功能變量，稱布爾函數 φ( X ) = φ(x1,x2,… ,xn)為n維向量X上的功能函數，簡稱功能函數，存在

功能函數本質上是把功能樹和布爾代數運算規則映射起來的紐帶，任意一棵含“與”、“或”、“非”門的功能樹都存在對應的功能函數，其計算依照布爾代數運算規則。

2 析取范式樹求解

2.1 任意功能樹相似度的計算障礙

相似理論[8]中的相似度計算方法在涵義上并未考慮“或”和“非”兩種系統要素組成的方式，因此，當試圖計算與或非功能樹之間的相似度時，發現簡單地套用基于相似理論的功能樹相似度計算方法[7]進行計算是不可行的，其存在的問題主要有以下3點：

1） 若兩棵功能樹的層高不同，則不滿足相似度計算的初始條件；

2） 若兩棵樹的門類型分布不同，即使層高相同，兩樹表達的實際意義也不同，因而直接計算存在意義偏差；

3） 若根據布爾代數運算法則整理兩樹的門類型，試圖使其保持一致，又由于與門、或門、非門 3種門類型的排列組合情況與功能樹的規模、節點排列方式等因素密切相關，則有可能導致復雜問題求解。

上述 3種情況是影響功能樹計算的主要因素，可見現有功能樹相似度計算方法不能有效解決任意兩棵功能樹的相似度計算問題。

2.2 析取范式樹的定義

定理1 設 E(x1,x2,… ,xn)是布爾代數＜ A,∨,∧,?＞上的任意一個布爾表達式，則它一定存在析取范式[9]。

由于功能函數φ ( X)是布爾表達式，則一棵功能樹所對應的 φ( X)必存在析取范式形式φd(X )，即化為積之和的形式，即其中 Di為表達式中第i個布爾積項，對應一個功能集δi，m為表達式中布爾積項的個數，并且Fi= {j|xjin Di}，(?) xj表示葉子節點 xj的門類型可能為非門。

同理，已知布爾函數φ ( X)，也可以畫出其所對應的功能樹。當φ ( X)化為析取范式形式之后，其對應的功能樹結構也相應發生變化。

定義3 析取范式樹 功能樹T存在功能函數φ ( X)，功能函數φ( X)存在析取范式φd(X)，φd(X )是功能樹 Td的功能函數，則稱任意功能樹 Td都是功能樹T的析取范式樹。

由于功能函數 φ( X)的析取范式φd(X)可能是不唯一的，所以功能樹T的析取范式樹 Td也可能是不唯一的。析取范式樹的形態和功能樹的初始形態、葉子節點的規定排序以及析取范式樹求解的過程等因素相關。由布爾定律知，φ( X)與φd(X )存在相同的真值表，因此，功能樹T與其析取范式樹 Td存在相同的解空間，可認為功能樹T等價于其析取范式樹 Td。

已知 φ( X)的析取范式φd(X)為積之和的形式，如果φd(X)只含有一個布爾積項，析取范式樹 Td是一棵根節點為與門的兩層功能樹，如圖1所示。如果φd(X )含有多個布爾積項，則析取范式樹 Td可能是一棵根節點為或門的兩層功能樹，如圖2所示。或者是只有根節點為或門的3層功能樹，如圖3所示。

圖1 兩層析取范式樹示例一

圖2 兩層析取范式樹示例二

當任意功能樹轉化為析取范式樹后，其析取范式樹的每個布爾積項都對應頂功能的一個解，從而可以通過比較布爾積項之間的相似程度來衡量功能樹之間的相似度，使得任意功能樹的相似度計算成為可能。

圖3 三層析取范式樹示例

將布爾函數化為析取范式形式常用的方法有真值法和公式化歸法[9]。真值法中，每個布爾變量可取0或1兩個值，若有n個布爾變量，則真值表有2n行，當布爾變量數量增加時，真值表的容量呈指數級增長，容易導致NP問題。公式化歸法在布爾代數運算法則的指導下從詞法的角度對布爾函數進行變換，是一種普遍使用的求解析取范式的方法。下面介紹兩種基于公式化歸法求解析取范式樹的具體算法。

2.3 門類型解析法

門類型解析法通過對節點門類型的判斷，對結構化的功能樹的節點直接進行相應的修改和增刪操作，通過依次執行“非門下降”、“或門提升”、“與門合并”3種基本操作，逐步調整功能樹的結構，最終變形為功能樹的析取范式樹。

1） 非門下降

根據布爾代數分配律，對功能樹中門類型為“與非”或“或非”的非葉子節點，將其非門下移至其子節點，使其本身的門類型變換為“與”或者“或”的過程，稱為功能樹的非門下降，如表1所示。

表1 非門下降的規則圖示

2） 或門提升

根據布爾代數分配律和結合律，對功能樹中門類型為“或”的非根非葉節點，將其或門上移至其父節點，使其父節點的門類型轉變或保持為“或”的結構變換過程，稱為功能樹的或門提升，如表2所示。

表2 或門提升的規則圖示

3） 與門合并

根據布爾代數結合律，對功能樹中父節點為“與”的非根節點，將其與父節點的與門合并的結構變換過程，稱為功能樹的與門合并，如表3所示。

表3 與門合并的規則圖示

門類型解析法的算法描述中，用戶從數據庫中讀取領域專家建立的功能樹后，選定其某一節點T，對以T為根的子樹求解其析取范式樹。其中，Q是暫存隊列，初始值為空。

（1） 若T為空或葉子節點，轉（10）。

（2） 查找T的子樹中門類型為“與非”或“或非”的節點Temp，若Temp為空，轉（5）。

（3） 若Temp不是葉子節點，對Temp執行非門下降，Q.push（Temp所有孩子節點）。

（4） 若 Q為空，轉（2）；否則，令Temp=Q.top()，Q.pop()，轉（3）。

（5） 查找T的子樹中門類型為“或”的非根非葉節點Temp，若Temp為空，轉（8）。

（6） 對Temp執行或門提升。

（7） 若Temp->parent不是T，令Temp=Temp ->parent，轉（6）；否則，轉（5）。

（8） 查找T的子樹中父節點為“與”的非根節點Temp，若Temp為空，轉（10）。

（9） 對Temp執行與門合并，轉（8）。（10） 返回T。

算法的輸出是一棵以T為根結點的新子樹，即為以T為根的原子樹的某一析取范式樹，它的結構只可能是兩層功能樹，或者只有根節點為或門的3層功能樹。

結點標識替換法可以對以字符類型記錄存儲的功能樹節點直接操作，通過依次執行“非門下降”、“標識替換”、“規范整理”3種基本操作，對輸入端的根節點標識字符進行分裂、替換、整理，得到功能樹析取范式形式 φd(X)的全部布爾積項的標識字符串，即可據此建立功能樹的析取范式樹。

1） 非門下降

此處的“非門下降”與門類型解析法的“非門下降”原理、步驟相同，不再贅述。

2） 標識替換

對功能樹中任一節點T，如果該節點不是葉子節點，則查詢該節點的門類型和子節點，進行相應字符替換。如果T是與門節點，則替換T為所有子節點的標識字符串；如果T是或門節點，且T有n個子節點，則先將T復制n-1次，再對n個T分別用其n個子節點標識字符進行替換，如表4所示。

表4 字符替換的規則

為方便字符操作，此處葉子節點的非門不以單獨的門類型標定，而是直接綁定葉子節點，在其標識字符加上標“’”，例如葉子節點x的非為x'，并將x與x' 看做不同的葉子節點，當x與x'同時出現時，不認為是字符x的重復。

3） 規范整理

潘金蓮作為《金瓶梅》中的第一女主角，對其進行分析的文章汗牛充棟。批評家對潘金蓮的態度由最開始的深惡痛絕，到后來的深表同情，直至最終保持客觀的評論，可以說是一個不斷從表層向深層理解的過程。潘金蓮是一個典型環境下的典型人物，她追求一切的欲望，小說中許多人物或多或少都有潘金蓮的影子。

對任一標識字符串執行“規范整理”，以使所有的標識字符串遵循同一規則，方便多個標識字符串的比較、排序等處理。首先要對節點標識字符串中的節點標識進行“排序”，排序的規則可以依據預先規定的節點標識排列順序。例如：字符串d, c, a, b, c, a根據字母表順序排序后得到字符串a, a, b, c, c, d。然后對排序過后的節點標識字符串進行“重復消除”，合并重復出現的標識，確保每個標識在字符串中僅出現一次。例如：字符串a, a, b, c, c, d消除重復后得到字符串a, b, c , d。

葉結點替換法的算法描述中，用戶讀取功能樹后選定某一節點T，求解以T為根的子樹其析取范式樹。其中，Q是暫存隊列，StrQ是布爾積項的字符串存儲隊列，StrTemp是暫存字符串，初始值均為空。

（1） 若T為空或葉子節點，轉（12）。

（2） 查找T的子樹中門類型為“與非”或“或非”的節點Temp，若Temp為空，轉（5）。

（3） 若Temp不是葉子節點，對Temp執行非門下降，Q.push（Temp所有子節點）。

（4） 若 Q為空，轉（2）；否則，令Temp=Q.top()，Q.pop()，轉（3）。

（5） StrQ.push(“T”)。

（6） StrTemp=StrQ.top()，StrQ.pop()，查找StrTemp中第1個非葉結點Temp，若Temp為空，轉（9）。

（7） 若Temp為與門節點，替換StrTemp中的 Temp為 Temp所有子節點標識的集合，StrQ.push(StrTemp)，轉（6）。

（8） 若Temp為或門節點，令n=Temp子節點數量，令StrTemp(i)=StrTemp，其中i=1,2,…,n，分別替換StrTemp(i)中的Temp為Temp第i個子節點標識，StrQ.push(StrTemp(i))，轉（6）。

（9） 對 StrQ中所有字符串分別進行標識排序。

（10） 對StrQ中所有字符串分別進行重復標識消除。

（11） 建立以T為根節點的析取范式樹。

（12） 返回T。

算法的輸出與門類型解析法相同，為以T為根的原子樹的某一析取范式樹。

3 任意功能樹的相似擴展

用可拓學[10]的物元[11]概念表示的功能稱為功能物元，物元之間的相似程度為物元相似度，基于人類相似聯想和對比聯想的物元相似度分別為物元一般相似度和物元對比相似度[12]。

定義4 物元一般相似度 兩物元Ra、Rb的特征數量分別為k、l，其中相同特征ci的數量為n，且 Ra、Rb在特征 ci上的特征一般相似度為simi(Ra,Rb)，取ci對相似程度影響的權重系數為ωi，則定義這兩物元的相似程度為物元一般相似度，計算方法為

定義5 物元對比相似度 兩物元Ra、Rb的特征數量分別為k、l，其中相反特征對cr、ct的數量為n對，且Ra、Rb在特征對cr、ct上的特征對比相似度為 simr′t(Ra,Rb)，取特征對cr、ct對相似程度影響的權重系數為ωi，則定義這兩物元的對比程度為物元對比相似度，計算方法為

概念設計中，設 ω= (ω1,ω2,… ωn)為領域專家給出的產品物元特征的權重向量，如果則需要重置ωi，令(ω1′,ω2′ ,… ωn′)，顯然再取ωi′為權重系數計算物元一般相似度 SIM(Ra,Rb)或物元對比相似度 SIM′(Ra,Rb)。

由于功能樹與其析取范式樹具有相同的解空間和布爾積項，因此，功能樹的相似度計算可以轉化為其析取范式樹的相似度計算。析取范式樹的每個布爾積項對應的子樹都是實現頂功能即設計需求的充分條件，可認為是實現設計需求的方案之一，因此計算析取范式樹的相似度也就是計算其布爾積項對應的子樹之間的相似度。由于析取范式樹一般都存在不止一個布爾積項，從而需要計算兩棵析取范式樹的布爾積項兩兩之間的相似度，再選取一個特殊值作為兩棵析取范式樹之間的相似度，習慣上一般選取最大值。

對任意兩棵功能樹T1、T2進行相似度計算的主要處理過程為：求解功能樹T1、T2的析取范式樹T1d、T2d；對T1d中的每一個布爾積項對應的子樹，分別使用物元相似度計算公式，與 T2d中的每一個布爾積項對應的子樹計算物元相似度，并記錄；按照預先設置的取值標準，取計算得到的所有物元相似度的最大值、最小值或平均值等作為功能樹T1和T2的相似度。

任意兩棵功能樹T1、T2的相似度計算的步驟如下：

1） 求解功能樹T1的析取范式樹T1d；

2） 求解功能樹T2的析取范式樹T2d；

3） 令 i= 1；

4） 查詢T1d的第i個布爾積項對應的子樹A1i，若不存在，轉10）；

5） 令j=1；

6） 查詢 T2d的第 j個布爾積項對應的子樹A2j，若不存在，轉9）；

7） 計算A1i與A2j的相似度；

8） 令j=j+1，轉6）；

9） 令i=i+1，轉4）；

10） 輸出A1i與A2j的相似度的最大值；

11） 結束。

計算功能樹的物元一般相似度和物元對比相似度后，判斷符合閾值要求，則可進行一般相似擴展和對比相似擴展[12]，獲得較原始功能樹蘊含更豐富信息的擴展功能樹。

4 設計過程的實例

為了展示概念設計中任意功能樹的可拓相似擴展過程，以多功能茶杯的設計為例，依次對其功能樹進行一般相似擴展和對比相似擴展。

1） 由領域專家根據設計需求進行功能分析，建立初始功能樹。圖4所示的初始功能樹，每個葉子節點下方的編號（如L1）為基本變量編號，每個門節點下方的編號（如 G1）為門變量編號。

2） 以圖4中或門節點G6為例，有兩個子功能“杯體雙層真空”和“杯體反射保溫”，查詢獲得以或門節點G17為根的子樹有4個子功能“杯體雙層真空”、“杯體保溫材料”、“杯體電加熱”和“杯體雙層中空”，根據任意功能樹的相似度計算方法計算G6和G17的物元一般相似度大于閾值，因此將 G17一般相似擴展入功能樹中。同理，可對初始功能樹進行對比相似擴展。

3） 圖5展示的擴展功能樹為對初始功能樹的多個節點進行一般相似擴展和對比相似擴展后的結果。

圖4 多功能茶杯的初始功能樹

圖5 對比相似擴展后的擴展功能樹

擴展功能樹較初始功能樹所蘊含的信息明顯有所增加，表5給出了實例擴展前后的數據分析。

表5 初始功能樹與擴展功能樹的分析對比表

5 結 論

使用現有功能樹相似度計算方法計算包含“與”、“或”、“非”3種門類型功能樹的相似度存在著難以逾越的障礙。因此，從功能樹與布爾代數的本然聯系出發，提出了析取范式樹的概念，以及兩種求解析取范式樹的算法，并描述了使用析取范式樹計算任意兩棵功能樹的相似度的方法。拓展了功能樹相似擴展方法的應用范圍，擴大了設計解空間，增加了獲得創新解的可能性。

析取范式樹雖然簡化并統一了復雜的功能樹結構，然而這種簡化必須以刪除中間節點及其信息為代價，對于強調中間節點信息的設計過程不適用。

[1] Hsu W, Liu B. Conceptual design: issues and challenges [J]. Computer Aided Design, 2000, 32(14): 849-850.

[2] Chakrabarti A, Thomas P, Bligh A. Scheme for functional reasoning in conceptual design [J]. Design Studies, 2001, 22(6): 493-517.

[3] Li Wenqiang, Li Yan, Wang Jian, el at. The process model to aid innovation of products conceptual design [J]. Expert Systems with Applications, 2010, 37(5): 3574-3587.

[4] Li Biqiong, Li Jie. Expert systems research for conceptual design of drilling fixture based on fuzzy algorithm [C]//Proceedings of 9th International Conference on Computer-Aided Industrial Design and Conceptual Design, 2008: 259-262.

[5] Zhang Hao, Zhang Jianhua, Liu Nian, el at. Function-oriented information assets identification on substation automation systems [C]//Proceedings of Asia-Pacific Power and Energy Engineering Conference, 2009: 1-4.

[6] Liu Xiaoping, Qin Jin, Tang Yiming. An innovative function-tree building method based on similarity theory and extension theory [C]//Proceedings of 7th International Conference on Computer-Aided Industrial Design and Conceptual Design, 2006: 1-6.

[7] 劉曉平, 陸勁挺, 唐益明. 基于可拓學的對比相似功能樹擴展方法[J]. 工程圖學學報, 2009, 30(1): 153-159.

[8] Zhou Meili. Principles of modeling of similar systems and feasibility analysis [J]. Journal of Systems Science and System Engineering, 1997, 6(4): 439-443.

[9] 左孝凌, 李為鑑, 劉永才. 離散數學[M]. 上海: 上海科學技術文獻出版社, 1982: 266-268.

[10] Zhu Qinhua, Yu Yongquan, Cai Wen. Extension set and the research of the extension ADD transformation [C]// Proceedings of 3rd International Conference on Information Technology and Applications, 2005: 399-402.

[11] Ju Yijing, Yu Yongquan, Ju Guangming, el at. Extension set and restricting qualifications of matter-elements' extension [C]//Proceedings of 3rd International Conference on Information Technology and Applications, 2005: 395-398.

[12] 陸勁挺. 概念設計中功能樹可拓相似推理方法研究[D]. 合肥: 合肥工業大學, 2009.

Method on similar extension of arbitrary function trees based on matter-element theory

Liu Xiaoping, Lu Jingting
( VCC Division, School of Computer & Information, Hefei University of Technology, Hefei Anhui 230009, China )

Function models are the core objects of conceptual design. Function tree is a typical function model which is widely used. Defects are found while the similarity of arbitrary function trees is calculated by existing method. Therefore, the concept of disjunctive normal form tree is proposed based on Boolean algebra. After that two solutions of Disjunctive normal form tree are presented. And a method on similarity calculation of arbitrary function trees is described. Thus, the application of function trees’ similar extension is expanded. As a result, the solution space is enlarged, and the possibility to attain innovational solutions increases. At last, an application example demonstrates the effectiveness of the method.

computer application; function tree; disjunctive normal form tree; matter-element similarity degree

TP 391

A

2095-302X (2012)04-0042-08

2010-12-31

國家自然科學基金資助項目（60673028）

劉曉平（1964-），男，山東濟南人，教授，主要研究方向為計算機圖形學、計算機輔助設計。