システムとモデリング

modelica, Julia, Design Structure Matrix, SysML, 他モデリング全般について。

DSMをJuliaのクラスタリングプログラムで整理する。

今回はDSM(Design Structure Matrix)のクラスタリングコードをJuliaで実装してみます。

クラスタリングアルゴリズムについては下記記事を参照してください。

otepipi.hatenablog.com

実際には以下の記事の擬似コードをJuliaで実装し直したものになります。

otepipi.hatenablog.com

Juliaのコード

実装したコードは以下のようになりました。

using LinearAlgebra

const powcc = 1;
const powbid = 0;
const powdep = 1;
const max_cluster_size = 61;
const rand_accept = 30;
const rand_bid = 30;
const times = 2;
const stable_limit = 2;

original_DSM=[ 0 1 0 0 1 1 0; 0 0 0 1 0 0 1; 0 1 0 1 0 0 1; 0 1 1 0 1 0 1; 0 0 0 1 0 1 0; 1 0 0 0 1 0 0; 0 1 1 1 0 0 0];

label = ["A","B","C","D","E","F","G"];
(DSMsize,) = size(original_DSM);


Clustermatrix = zeros(DSMsize,DSMsize) + Diagonal(ones(DSMsize,DSMsize)) ;

DSM = original_DSM;


function ClusterBid(Clustermatrix,DSM,DSMsize,powdep,powbid,element)

    bestCluster = 0;
    bestBid = -1;

    for i = 1 : DSMsize

        Clusterlist= findall(x-> x == 1 , Clustermatrix[i,:]);
        (Clustersize,) = size(Clusterlist);
        bid = 0;

        for j = 1 : Clustersize

            bid += DSM[element,Clusterlist[j]];

        end

        bid = bid ^ powdep / Clustersize ^ powbid;

        if bid > bestBid

             bestBid = bid;
            bestCluster = i;
        end

    end


    return bestCluster

end

function TCC(DSM,DSMsize,Clustermatrix,powcc)

    intraCost=0;
    extraCost=0;


    for i = 1: DSMsize
    
        for j = 1 : DSMsize

            Clusterofi = findall(x-> x == 1 , Clustermatrix[:,i]);
            Clusterofj = findall(x-> x == 1 , Clustermatrix[:,j]);
            (Clustersizeofi,) = size(Clustermatrix[Clusterofi,:]);

            cost = DSM[i,j] + DSM[j,i];

            if Clusterofi == Clusterofj

                intraCost += cost*Clustersizeofi^powcc;

            else

                extraCost += cost*DSMsize^powcc;
            end


        end
    
    end

    totalCost = intraCost + extraCost;

    return totalCost
end


TCCost = TCC(DSM,DSMsize,Clustermatrix,powcc)

costlist = zeros(DSMsize*times,1);

for i = 1 : DSMsize * times;

    preClustermatrix = Clustermatrix;
    element = rand(1:DSMsize);
    bestCluster = ClusterBid(Clustermatrix,DSM,DSMsize,powdep,powbid,element);
    Clustermatrix[:,element] = zeros(DSMsize,1);
    Clustermatrix[bestCluster,element] = 1;
    newCost = TCC(DSM,DSMsize,Clustermatrix,powcc);
    if newCost <= maximum([TCCost,rand_accept])
        global TCCost = newCost;
    else
       global Clustermatrix = preClustermatrix;
    end

    global costlist[i] = newCost
end

Clustermatrix
costlist'

これを使って実際に試してみます。

例題

以下のDSMクラスタリングしてみます。

f:id:Otepipi:20190512195427p:plain

下記パラメーターの元で今回のプログラムを実行してみます。 パラメーターの最適化はまだできてないです。

const powcc = 1;
const powbid = 0;
const powdep = 1;
const max_cluster_size = 61;
const rand_accept = 30;
const rand_bid = 30;
const times = 2;
const stable_limit = 2;

今回のプログラムより以下のことがわかります。

クラスタ 要素
クラスター1 A, E, F
クラスター2 B, C, D, G

この情報から先程のDSMを並び替えてみます。

f:id:Otepipi:20190519164134p:plain

たしかにクラスタリング前と比べると対角線に非ゼロ要素が集まるようになりました。 次のステップは、自動でDSMを並べ替えて描画までを考えています。

今回はここまでにします。